| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题居然能暴力!!!4000ms啊。。。一点没优化都过了#include<stdio.h>
#include<string.h>
using namespace std;
int pre[1005];
int n,d;
void init(){
for(int i=1;i<=n;i++)
pre[i]=i;
}
int find(int x){
while(x!=pre[x])
x=pre[x];
return x;
}
struct node { int x,y,id,vis;}a[1010];
bool dis(int i,int j)
{
if(((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))>d*d)
return false;
else return true;
}
int main(){
scanf("%d%d",&n,&d);
init();
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id=i;
a[i].vis=0;
}
char s[5];
int v,u;
while(scanf("%s",&s)!=EOF){
if(s[0]=='S'){
scanf("%d%d",&v,&u);
int dx=find(v);
int dy=find(u);
if(pre[dx]!=pre[dy])
printf("FAIL\n");
else printf("SUCCESS\n");
}
if(s[0]=='O'){
scanf("%d",&v);
a[v].vis=1;
int dx=find(v);
for(int i=1;i<=n;i++){
if(a[i].vis&&dis(v,i)&&v!=i){
int dy=find(i);
if(dx!=dy){
pre[dy]=dx;
}
}
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator