首页 > ACM题库 > HDU-杭电 > HDU 3622-Bomb Game-分治-[解题报告]HOJ
2014
11-29

HDU 3622-Bomb Game-分治-[解题报告]HOJ

Bomb Game

问题描述 :

Robbie is playing an interesting computer game. The game field is an unbounded 2-dimensional region. There are N rounds in the game. At each round, the computer will give Robbie two places, and Robbie should choose one of them to put a bomb. The explosion area of the bomb is a circle whose center is just the chosen place. Robbie can control the power of the bomb, that is, he can control the radius of each circle. A strange requirement is that there should be no common area for any two circles. The final score is the minimum radius of all the N circles.
Robbie has cracked the game, and he has known all the candidate places of each round before the game starts. Now he wants to know the maximum score he can get with the optimal strategy.

输入:

The first line of each test case is an integer N (2 <= N <= 100), indicating the number of rounds. Then N lines follow. The i-th line contains four integers x1i, y1i, x2i, y2i, indicating that the coordinates of the two candidate places of the i-th round are (x1i, y1i) and (x2i, y2i). All the coordinates are in the range [-10000, 10000].

输出:

The first line of each test case is an integer N (2 <= N <= 100), indicating the number of rounds. Then N lines follow. The i-th line contains four integers x1i, y1i, x2i, y2i, indicating that the coordinates of the two candidate places of the i-th round are (x1i, y1i) and (x2i, y2i). All the coordinates are in the range [-10000, 10000].

样例输入:

2
1 1 1 -1
-1 -1 -1 1
2
1 1 -1 -1
1 -1 -1 1

样例输出:

1.41
1.00

/*
二分+2-sat
题意:在一个二维平面上给你n个炸弹,和2*n个位置,每一行的两个位置只能有一个放炸弹
现在炸弹爆炸有一个半径,当炸弹爆炸时两个炸弹的半径化成的圆不能相交,求最大半径
二分半径,
每次如果一个炸弹可放的两个位置中的一个与其他位置有矛盾,就进行建边,最后判断是否存在这样一组解
即可。
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define eps 1e-5
#define N 210
struct node {
int u,v,next;
}bian[N*N];
int head[N],dfn[N],low[N],stac[N],yong,index,top,vis[N],ans,belong[N];
void init() {
memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(stac,0,sizeof(stac));yong=0;index=0;top=0;;memset(vis,0,sizeof(vis));ans=0;
memset(belong,0,sizeof(belong));
}
void addedge(int u,int v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
int Min(int v,int vv) {
return v>vv?vv:v;
}
void tarjan(int u) {
  dfn[u]=low[u]=++index;
  stac[++top]=u;
  vis[u]=1;
  int i;
  for(i=head[u];i!=-1;i=bian[i].next) {
    int v=bian[i].v;
    if(!dfn[v]) {
        tarjan(v);
        low[u]=Min(low[u],low[v]);
    }
    else
        if(vis[v])
        low[u]=Min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    ans++;
    int t;
    do {
        t=stac[top--];
        belong[t]=ans;
        vis[t]=0;
    }while(t!=u);
  }
}
struct nodee{
int u,v,index;
}f[N*N];
int n;
double distance(nodee d,nodee dd) {
return 1.0*(d.u-dd.u)*(d.u-dd.u)+1.0*(d.v-dd.v)*(d.v-dd.v);
}
int judge(double r) {
  int i,j;
  init();
     for(i=0;i<2*n-1;i++)
      for(j=i+1;j<2*n;j++) {
        if(i==(j^1))continue;
       if(distance(f[i],f[j])<(r*2)*(r*2)) {//如果有冲突就进行
        addedge(i,j^1);
        addedge(j,i^1);
       }
      }
      for(i=0;i<2*n;i++)
        if(!dfn[i])
            tarjan(i);
    for(i=0;i<n;i++)
        if(belong[i*2]==belong[i*2+1])break;
    if(i==n)return 1;
    return 0;
}
int main() {
   int i;
   double left,right,mid;
   while(scanf("%d",&n)!=EOF) {
      for(i=0;i<n;i++)
        scanf("%d%d%d%d",&f[i*2].u,&f[i*2].v,&f[i*2+1].u,&f[i*2+1].v);
      right=2*10000.0*2;left=0.0;
      while(right-left>eps) {
        mid=(left+right)/2;
      //  printf("%.2f\n",mid);
        if(judge(mid))left=mid+eps;
        else
            right=mid-eps;
      }
      printf("%.2f\n",left);
   }
return 0;}

参考:http://blog.csdn.net/u011483306/article/details/40212507


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count