pukpuk

Untitled

Jun 24th, 2013
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.94 KB | None | 0 0
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<vector>
  5. using namespace std;
  6. struct S{
  7.        int x,y;
  8.        };
  9. S edges[205];
  10. S points[205];
  11. int set[205];
  12. int getparent(int i)
  13. {
  14.     if(set[i]==i) return i;
  15.     else return(set[i]=getparent(set[i]));
  16. }
  17. int isunion(int a,int b)
  18. {
  19.     return (getparent(a)==getparent(b));
  20. }
  21. void makeunion(int a,int b)
  22. {
  23.      set[getparent(a)]=getparent(b);
  24. }
  25. bool same(S a,S b)
  26. {
  27.    return (a.x==b.x && a.y==b.y);  
  28. }
  29. inline int sameline(S a,S c,S b)//computes area of tringle area,if 0,then same line
  30. {
  31.    int area=a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
  32.    return area;
  33. }
  34. inline bool online(S a,S b,S c)//checks if c lies on ab line segment
  35. {
  36.     int minX,minY,maxX,maxY;
  37.     minX=min(a.x,b.x);minY=min(a.y,b.y);
  38.     maxX=max(a.x,b.x);maxY=max(a.y,b.y);
  39.     if(c.x>=minX && c.x<=maxX && c.y>=minY && c.y<=maxY) return true;
  40.     else return false;  
  41. }
  42. inline bool sign(int a,int b)//checks if they have diffrent signs
  43. {
  44.    if(a>0 && b<0) return true;
  45.    if(a<0 && b>0) return true;
  46.    return false;    
  47. }
  48. inline bool intersect(S A,S B,S p,S q)//checks
  49. {
  50.    long long int m1,m2,m3,m4;
  51.    m1=sameline(A,B,p);
  52.    m2=sameline(A,B,q);
  53.    m3=sameline(p,q,A);
  54.    m4=sameline(p,q,B);
  55.    if(sign(m1,m2) && sign(m3,m4)) return true;
  56.    else if(m1==0 &&  online(A,B,p)) return true;
  57.    else if(m2==0 && online(A,B,q)) return true;
  58.    else if(m3==0 && online(p,q,A)) return true;
  59.    else if(m4==0 && online(p,q,B)) return true;
  60.    else return false;  
  61. }
  62. int main()
  63. {
  64.     int n,m,i,j,a,b;
  65.     while(scanf("%d%d",&n,&m)!=EOF)
  66.     {
  67.        for(i=1; i<=n; i++)  scanf("%d%d",&points[i].x,&points[i].y);
  68.        for(i=1; i<=m; i++)  scanf("%d%d",&edges[i].x,&edges[i].y);
  69.        for(i=1; i<=n; i++) set[i]=i;
  70.        for(i=1; i<=m; i++)
  71.        {
  72.           a=edges[i].x;b=edges[i].y;
  73.           if(!isunion(a,b))  makeunion(a,b);    
  74.        }
  75.        for(i=1; i<=m; i++)
  76.        {
  77.           for(j=i+1; j<=m; j++)
  78.           {
  79.              S A,B,C,D;
  80.              A=points[edges[i].x];
  81.              B=points[edges[i].y];
  82.              C=points[edges[j].x];
  83.              D=points[edges[j].y];
  84.              if(same(A,C)||same(A,D)||same(B,C)||same(B,D))
  85.              {
  86.                 if(!isunion(edges[i].x,edges[j].x))
  87.                    makeunion(edges[i].x,edges[j].x);                                          
  88.              }
  89.              else if(intersect(A,B,C,D))
  90.              {
  91.                 if(!isunion(edges[i].x,edges[j].x))
  92.                    makeunion(edges[i].x,edges[j].x);  
  93.              }
  94.           }      
  95.        }
  96.        
  97.        int tmp,p=getparent(1);
  98.        bool f=true;
  99.        for(i=2; i<=n; i++)
  100.        {
  101.           tmp=getparent(i);
  102.           if(tmp!=p)
  103.           {
  104.              f=false;break;        
  105.           }      
  106.        }
  107.        if(f)  printf("YES\n");
  108.        else printf("NO\n");                            
  109.     }
  110.     return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment