2014
11-29

# 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

/*

*/
#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];
void init() {
memset(stac,0,sizeof(stac));yong=0;index=0;top=0;;memset(vis,0,sizeof(vis));ans=0;
memset(belong,0,sizeof(belong));
}
bian[yong].u=u;
bian[yong].v=v;
}
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;
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)) {//如果有冲突就进行
}
}
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;}


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