WA on test 9
What's wrong?
#include<cstdio>
using namespace std;
const int N=201;
struct Node{int x,y;}a[N];
struct Line{int s,t;}b[N];
int fa[N],n,m,root;
inline int direct(Node x,Node y,Node z){
return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
}
bool online(Node x,Line y){//right
Node be=a[y.s],en=a[y.t];
if (x.x<be.x||x.x>en.x) return 0;
if (direct(be,x,en)==0) return 1;
return 0;
}
bool cross(Line x,Line y){
Node p1=a[x.s],p2=a[x.t],p3=a[y.s],p4=a[y.t];
if (online(p1,y)||online(p2,y)||online(p3,x)||online(p4,x)) return 1;
int d1=direct(p1,p2,p3),d2=direct(p1,p2,p4),d3=direct(p3,p4,p1),d4=direct(p3,p4,p2);
if ((d1^d2)<0&&(d3^d4)<0) return 1;
return 0;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){
x=find(x); y=find(y);
if (x<y) fa[y]=x; else if (x>y) fa[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) fa[i]=i;
for (int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y);
for (int i=1; i<=m; i++){
scanf("%d%d",&b[i].s,&b[i].t); unite(b[i].s,b[i].t);
for (int j=1; j<=n; j++)if (online(a[j],b[i])) unite(j,b[i].s);
for (int j=1; j<i; j++) if (cross(b[i],b[j])) unite(b[i].s,b[j].s);
}
root=find(1);
for (int i=2; i<=n; i++) if (find(i)!=root) {printf("NO"); return 0;}
printf("YES");
return 0;
}