Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<vector>
- using namespace std;
- struct S{
- int x,y;
- };
- S edges[205];
- S points[205];
- int set[205];
- int getparent(int i)
- {
- if(set[i]==i) return i;
- else return(set[i]=getparent(set[i]));
- }
- int isunion(int a,int b)
- {
- return (getparent(a)==getparent(b));
- }
- void makeunion(int a,int b)
- {
- set[getparent(a)]=getparent(b);
- }
- bool same(S a,S b)
- {
- return (a.x==b.x && a.y==b.y);
- }
- inline int sameline(S a,S c,S b)//computes area of tringle area,if 0,then same line
- {
- 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;
- return area;
- }
- inline bool online(S a,S b,S c)//checks if c lies on ab line segment
- {
- int minX,minY,maxX,maxY;
- minX=min(a.x,b.x);minY=min(a.y,b.y);
- maxX=max(a.x,b.x);maxY=max(a.y,b.y);
- if(c.x>=minX && c.x<=maxX && c.y>=minY && c.y<=maxY) return true;
- else return false;
- }
- inline bool sign(int a,int b)//checks if they have diffrent signs
- {
- if(a>0 && b<0) return true;
- if(a<0 && b>0) return true;
- return false;
- }
- inline bool intersect(S A,S B,S p,S q)//checks
- {
- long long int m1,m2,m3,m4;
- m1=sameline(A,B,p);
- m2=sameline(A,B,q);
- m3=sameline(p,q,A);
- m4=sameline(p,q,B);
- if(sign(m1,m2) && sign(m3,m4)) return true;
- else if(m1==0 && online(A,B,p)) return true;
- else if(m2==0 && online(A,B,q)) return true;
- else if(m3==0 && online(p,q,A)) return true;
- else if(m4==0 && online(p,q,B)) return true;
- else return false;
- }
- int main()
- {
- int n,m,i,j,a,b;
- while(scanf("%d%d",&n,&m)!=EOF)
- {
- for(i=1; i<=n; i++) scanf("%d%d",&points[i].x,&points[i].y);
- for(i=1; i<=m; i++) scanf("%d%d",&edges[i].x,&edges[i].y);
- for(i=1; i<=n; i++) set[i]=i;
- for(i=1; i<=m; i++)
- {
- a=edges[i].x;b=edges[i].y;
- if(!isunion(a,b)) makeunion(a,b);
- }
- for(i=1; i<=m; i++)
- {
- for(j=i+1; j<=m; j++)
- {
- S A,B,C,D;
- A=points[edges[i].x];
- B=points[edges[i].y];
- C=points[edges[j].x];
- D=points[edges[j].y];
- if(same(A,C)||same(A,D)||same(B,C)||same(B,D))
- {
- if(!isunion(edges[i].x,edges[j].x))
- makeunion(edges[i].x,edges[j].x);
- }
- else if(intersect(A,B,C,D))
- {
- if(!isunion(edges[i].x,edges[j].x))
- makeunion(edges[i].x,edges[j].x);
- }
- }
- }
- int tmp,p=getparent(1);
- bool f=true;
- for(i=2; i<=n; i++)
- {
- tmp=getparent(i);
- if(tmp!=p)
- {
- f=false;break;
- }
- }
- if(f) printf("YES\n");
- else printf("NO\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment