POJ2236
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; struct node { int x,y; }v[1100]; int d,n; int dp[1100][1100]; int vis[1100],pre[1100]; int dis(int a,int b) { double temp=(v[a].x-v[b].x)*(v[a].x-v[b].x)+(v[a].y-v[b].y)*(v[a].y-v[b].y); temp=sqrt(temp); if(temp<=d) return 1; return 0; } int Find(int x) { if(pre[x]!=x) return Find(pre[x]); return x; } void howhead(int x,int y) { int headx=Find(x); int heady=Find(y); if(headx!=heady) { pre[headx]=heady; } } int main() { // freopen("C:\\Users\\方瑞\\Desktop\\input.txt","r",stdin); // freopen("C:\\Users\\方瑞\\Desktop\\output.txt","w",stdout); cin>>n>>d; FOR(i,1,n) { cin>>v[i].x>>v[i].y; } FOR(i,1,n) { FOR(j,i,n) { if(dis(i,j)) { dp[i][j]=1; dp[j][i]=1; } } } FOR(i,1,n) pre[i]=i; char c; while(cin>>c) { if(c=='O') { int hhh ; cin>>hhh; vis[hhh]=1; //注意这个位置================================ for(int i=1;i<=n;++i) { if(vis[i]==1 && dp[hhh][i]==1) { howhead(i,hhh); } } } else { int a,b; cin>>a>>b; if(Find(a)==Find(b)) cout<<"SUCCESS"<<endl; else cout<<"FAIL"<<endl; } } }
转载于:https://www.cnblogs.com/jrfr/p/11260069.html
