您现在的位置是:首页 > web开发 > POJ 2236 Wireless Network

POJ 2236 Wireless Network

web开发作者:dayu日期:9天前点击:3
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n; double r; vector<int>g[1001]; int fa[1001]; bool online[1001]; struct node { double x,y; } point[1001]; int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } double getlen(node a,node b) { double len=sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)); return len-r; } int main() { scanf("%d%lf",&n,&r); for(int i=1; i<=n; i++) scanf("%lf%lf",&point[i].x,&point[i].y); for(int i=1; i<=n; i++) fa[i]=i,g[i].clear(); int cot=0; for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) { double len=getlen(point[i],point[j]); if(len<=0) { g[i].push_back(j); g[j].push_back(i); } } memset(online,0,sizeof(online)); char str[10]; while(scanf("%s",str)!=EOF) { if(str[0]=='S') { int a,b; scanf("%d%d",&a,&b); if(father(a)!=father(b)) puts("FAIL"); else puts("SUCCESS"); } else if(str[0]=='O') { int u; scanf("%d",&u); online[u]=1; for(int j=0; j<g[u].size(); j++) { int v=g[u][j]; if(!online[v])continue; v=father(v); if(u==v)continue; fa[v]=u; } } } }


POJ 2236 Wireless Network

原文地址:http://www.cnblogs.com/zhchoutai/p/7252417.html


下一篇       上一篇