Cod sursa(job #387568)

Utilizator costyv87Vlad Costin costyv87 Data 27 ianuarie 2010 21:57:18
Problema Poligon Scor 40
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.1 kb
type punct=record
        x,y:longint;
        end;
var f,g:text;
    v:array[1..1000] of punct;
    con2,n,i,con,j,m:longint;
    ok:boolean;
    x1,x2,x3,Ax,Ay,Bx,By,a1,a2,b1,b2,c1,c2,x,y,min:real;
    minn,max:punct;
begin
assign(f,'poligon.in'); reset(f);
assign(g,'poligon.out'); rewrite(g);
read(f,n,m);
min:=maxlongint;
for i:=1 to n do begin
read(f,v[i].x,v[i].y);
if v[i].x<min then min:=v[i].x;
end;
con2:=0;
for j:=1 to m do begin
read(f,Ax,Ay);
Bx:=min-1;
By:=Ay;
a2:=By-Ay;
b2:=-Bx+Ax;
c2:=Ay*Bx-Ax*By;
X:=0; Y:=0;
con:=0;
ok:=true;
v[n+1]:=v[1];
for i:=1 to n do begin
a1:=v[i+1].y-v[i].y;
b1:=-v[i+1].x+v[i].x;
c1:=v[i].y*v[i+1].x-v[i].x*v[i+1].y;

if (a1*b2<>a2*b1)
    and ((Ax*a1+Ay*b1+c1)*(Bx*a1+By*b1+c1)<=0)
    and ((v[i].x*a2+v[i].y*b2+c2)*(v[i+1].x*a2+v[i+1].y*b2+c2)<=0)
        then begin
                        X:=(b1*c2-b2*c1)/(a1*b2-a2*b1);
                        Y:=(c1*a2-c2*a1)/(a1*b2-a2*b1);
                        max:=v[i];  minn:=v[i+1];
                        if v[i+1].y>max.y then begin
                                               max:=v[i+1];
                                               minn:=v[i];
                                                end;
                        if ((x<>minn.x) or (y<>minn.y)) {and
    (sqrt(sqr(v[i].x-v[i+1].x)+sqr(v[i].y-v[i+1].y))
    -sqrt(sqr(x-v[i].x)+sqr(y-v[i].y))+sqrt(sqr(x-v[i+1].x)+sqr(y-v[i+1].y))<0.000000001)}  then inc(con);
                        end;
x1:=sqrt(sqr(v[i].x-v[i+1].x)+sqr(v[i].y-v[i+1].y));
x2:=sqrt(sqr(Ax-v[i].x)+sqr(Ay-v[i].y));
x3:=sqrt(sqr(Ax-v[i+1].x)+sqr(Ay-v[i+1].y));
if abs(x1-x2-x3)<0.0000000001 then begin
                                                                               inc(con2);
                                                                               ok:=false;
                                                                               break;
                                                                               end;
end;
if ok then begin if con mod 2=1 then inc(con2);
             end;
end;
writeln(g,con2);
close(g);
end.