please help

Probably you're getting overflow

\/ \/
/\ /\

8 4
0 0
2 2
2 0
0 2
0 3
2 5
2 3
0 5
1 2
3 4
5 6
7 8

Answer: "NO"

This probably helps

3 1
0 0
2 2
3 3
1 3

Ans: YES

3 1
0 5
2 5
3 5
1 2

Ans: NO

Input:
4 2
1 1
5 3
7 -1
4 7
1 2
3 4

Correct output:
NO

One of the reasons of "WA" might be that your solution incorrectly determines whether two segments intersect or not.

Edited by author 11.04.2020 15:09

One of my AC solution get AC, but on this test get answer "NO". (Correct answer is "YES").
4 2
-30000 -30000
30000 -30000
30000 30000
-30000 30000
1 3
4 2

I tried everything and cannot pass the second test .. any help?

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;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#define pii pair<int,int>
#define pdd pair<double,double>
#define mp make_pair
#define F first
#define S second
#define N 210
using namespace std;
int n,m;
int fat[N];
pii e[N];
pdd p[N];
int father(int x) {if(fat[x]!=x) fat[x]=father(fat[x]); return fat[x];}
double calc(pii a,pii b,pii c)  {return (a.F-c.F)*(b.S-c.S)-(b.F-c.F)*(a.S-c.S);}
bool judge(pii a, pii b, pii c, pii d)
{
    if (max(a.F,b.F)<min(c.F,d.F)||max(a.S,b.S)<min(c.S,d.S)||max(c.F,d.F)<min(a.F,b.F)||max(c.S,d.S)<min(a.S,b.S))  return false;
    if (calc(c,b,a)*calc(b,d,a)<0||calc(a,d,c)*calc(d,b,c)<0)  return false;
    return true;
}
int main()
{
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) fat[i]=i;
    for(i=1;i<=n;i++) {scanf("%lf %lf",&x,&y); p[i]=mp(x,y);}
    for(i=1;i<=m;i++) {scanf("%d %d",&x,&y); e[i]=mp(x,y); fat[father(x)]=father(y);}
    for(i=m+1;i<=m+n;i++) e[i]=mp(i-m,i-m);
    m+=n;
    for(i=1;i<=m;i++)
        for(j=i+1;j<=m;j++)
            if(judge(p[e[i].F],p[e[i].S],p[e[j].F],p[e[j].S]))
                fat[father(e[i].F)]=father(e[j].F);
    int stan=father(1);
    for(i=1;i<=n;i++) if(father(i)!=stan)
    puts("YES");
    return 0;
}

const Nmax=500;
var
 Stx,Sty,xx1,yy1,xx2,yy2:array[1..Nmax] of real;
 numb1,numb2:array[1..Nmax] of integer;
 a:array[1..Nmax,1..Nmax] of boolean;
 Nnew:array[1..Nmax] of boolean;
 N,M,i,j,r,n1,n2:integer;
 ans:string;

procedure Peres(x1,y1,x2,y2,x3,y3,x4,y4:real);
var
 x0,y0:real;
 A1,B1,C1,A2,B2,C2,Det:real;
begin
 ans:='No';

 if(x1>x2) then begin
  x0:=x1;
  y0:=y1;
  x1:=x2;
  y1:=y2;
  x2:=x0;
  y2:=y0;
 end;
 if(x3>x4) then begin
  x0:=x3;
  y0:=y3;
  x3:=x4;
  y3:=y4;
  x4:=x0;
  y4:=y0;
 end;

 A1:=y1-y2;
 B1:=x2-x1;
 C1:=x1*y2-y1*x2;

 A2:=y3-y4;
 B2:=x4-x3;
 C2:=x3*y4-y3*x4;

 Det:=A1*B2-A2*B1;

 if(x3=x4)and(y3=y4) then begin
  if(A1*x3+B1*y3+C1=0)and((x1-x3)*(x2-x3)+(y1-y3)*(y2-y3)<=0) then ans:='Yes';
 end
 else begin
  if(Det<>0) then begin
    x0:=(C2*B1-C1*B2)/Det;
    y0:=(C1*A2-C2*A1)/Det;
    if((x1-x0)*(x2-x0)+(y1-y0)*(y2-y0)<=0)and((x3-x0)*(x4-x0)+(y3-y0)*(y4-y0)<=0) then ans:='Yes';
  end
  else begin
   if(A2*x1+B2*y1+C2=0) then begin
    if(x1<=x3)and(x3<=x2) then ans:='Yes';
    if(x1<=x4)and(x4<=x2) then ans:='Yes';
    if(x3<=x1)and(x1<=x4) then ans:='Yes';
    if(x3<=x2)and(x2<=x4) then ans:='Yes';
   end;
  end;
 end;
end;

procedure G(v:integer);
 var u:integer;
begin
 Nnew[v]:=false;
 for u:=1 to N do begin
  if(Nnew[u])and(a[v,u]) then begin G(u);end;
 end;
end;

BEGIN
 readln(N,M);
 for i:=1 to N do begin
 for j:=1 to N do begin
  a[i,j]:=false;
 end;
 end;

 for i:=1 to N do begin
  readln(Stx[i],Sty[i]);
  Nnew[i]:=true;
 end;

 r:=0;

 for i:=1 to M do begin
  readln(n1,n2);
  a[n1,n2]:=true;
  a[n2,n1]:=true;
  inc(r);
  xx1[r]:=Stx[n1];
  yy1[r]:=Sty[n1];
  xx2[r]:=Stx[n2];
  yy2[r]:=Sty[n2];
  numb1[r]:=n1;
  numb2[r]:=n2;

  for j:=1 to r-1 do begin
   Peres(xx1[j],yy1[j],xx2[j],yy2[j],Stx[n1],Sty[n1],Stx[n2],Sty[n2]);
   if(ans='Yes') then begin
    a[n1,numb1[j]]:=true;
    a[n1,numb2[j]]:=true;
    a[numb1[j],n1]:=true;
    a[numb1[j],n2]:=true;
    a[n2,numb1[j]]:=true;
    a[n2,numb2[j]]:=true;
    a[numb2[j],n1]:=true;
    a[numb2[j],n2]:=true;
   end;
  end;
 end;


 for i:=1 to N do begin
 for j:=1 to r do begin
  Peres(xx1[j],yy1[j],xx2[j],yy2[j],Stx[i],Sty[i],Stx[i],Sty[i]);
   if(ans='Yes') then begin
    a[i,numb1[j]]:=true;
    a[i,numb2[j]]:=true;
    a[numb1[j],i]:=true;
    a[numb2[j],i]:=true;
   end;
  end;
 end;

 G(1);
 ans:='YES';
 for i:=1 to N do if(Nnew[i]) then ans:='NO';
 write(ans);
END.

Please test this case:

4 2
0 0
1 0
2 0
3 0
1 2
3 4

Answer: NO

Edited by author 22.06.2013 15:11