ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1966. Cycling Roads

Where is mistake? Who knows test 9?
Posted by Felix_Mate 14 Nov 2015 00:23
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.