A - Wireless Network POJ - 2236

제목 의 대의:
         지진 으로 컴퓨터 의 통신 이 고 장 났 지만 수리 중 입 니 다. "O 1" 을 입력 하면 1 번 컴퓨터 가 고 쳐 졌 다 는 뜻 입 니 다. "S 1 2" 를 입력 하면 두 컴퓨터 가 통신 할 수 있 는 지 물 어 보 는 뜻 입 니 다.두 컴퓨터 사이 의 거리 가 d 보다 작 을 때 만 통신 할 수 있 도록 규정 하고 있다. 만약 에 A, B 가 통신 할 수 있 고 B 가 C 와 통신 할 수 있다 면 A 도 C 와 통신 할 수 있다.첫 번 째 줄 에 N, d, N 을 입력 하면 몇 대의 컴퓨터 가 있 고 d 는 최 장 거 리 를 표시 합 니 다.다음 N 줄, i 줄 은 i 번 째 컴퓨터 의 좌 표를 표시 합 니 다.다음 입력 동작.질문 할 때 'SUCCESS' 나' FAIL '을 출력 합 니 다.(입력 줄 수가 3 만 줄 을 넘 지 않 음)
참고 방향:
     자신의: 수리 에 성공 한 컴퓨터 를 입력 하여 그 를 저장 하고 앞에서 이미 고 친 컴퓨터 와 판단 해 보 세 요. 판단 조건 은 1. 이미 고 친 것 입 니 다.2. 거리 가 작은 것.연결 이 된 후 질문 에 부 딪 혔 을 때 이 두 점 의 근결 점 이 같 는 지 살 펴 보 세 요.
참조 코드:
 
  1 #include 
  2 #include 
  3 #include 
  4 #include <string>
  5 #include 
  6 #include 
  7 #include <set>
  8 
  9 #include 
 10 #include 
 11 #include 
 12 #include 
 13 using namespace std;
 14 
 15 const int INF=0x3f3f3f3f;
 16 const int SIZE=1e3+10;
 17 
 18 struct node{
 19     int id;
 20     int fix;  ///
 21     double x,y;
 22 }cmt[SIZE] ;
 23 
 24 int sz[SIZE];
 25 int n;
 26 double d;
 27 ///
 28 
 29 double dis(int p,int q)
 30 {
 31     double temp=(cmt[p].x-cmt[q].x)*(cmt[p].x-cmt[q].x)+(cmt[p].y-cmt[q].y)*(cmt[p].y-cmt[q].y); ///  
 32 
 33     return temp;
 34 }
 35 int find(int x)
 36 {
 37     while(cmt[x].id!=x)
 38     {
 39         cmt[x].id=cmt[cmt[x].id].id;
 40         x=cmt[x].id;
 41     }
 42     return x;      ///     
 43 }
 44 bool connect(int p,int q)
 45 {
 46     return find(p)==find(q);
 47 }
 48 
 49 void un(int p,int q)
 50 {
 51 
 52     if(cmt[q].fix==0||dis(p,q)>d*d) return;  ///   ?    ?
 53     int pr=find(p);
 54     int qr=find(q);
 55 
 56     if(pr==qr) return ;  ///       
 57     if(sz[pr]qr;}
 58     else {sz[pr]+=sz[qr];cmt[qr].id=pr;}//cout<
 59 }
 60 
 61 void clear()
 62 {
 63     for(int i=1;i<=n;i++)
 64         sz[i]=1;
 65 }
 66 
 67 int main()
 68 {
 69     int i,j;
 70     cin>>n>>d;
 71     clear();
 72     for(i=1;i<=n;i++)
 73     {
 74         cin>>cmt[i].x>>cmt[i].y;
 75         cmt[i].fix=0;
 76         cmt[i].id=i;
 77     }
 78     char x;
 79     int temp,a,b;
 80     while(cin>>x)
 81     {
 82         if(x=='O')
 83         {
 84             cin>>temp;
 85             cmt[temp].fix=1;  ///   
 86             for(i=1;i<=n;i++)
 87                 if(i!=temp)
 88                    un(temp,i);
 89         }
 90         else
 91         {
 92             cin>>a>>b;
 93             if(!connect(a,b)) cout<<"FAIL
"; 94 else cout<<"SUCCESS
"; 95 } 96 } 97 return 0; 98 } 99 100 ///http://blog.csdn.net/dm_vincent/article/details/7655764 ( ) 101

 
 
 
  
     
 
다음으로 전송:https://www.cnblogs.com/xxQ-1999/p/7469771.html

좋은 웹페이지 즐겨찾기