fence4.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:fence4
}

program fence4;
const
  maxn=199;
  zero=1e-6;
var
  fin,fout:text;
  x,y:array[1..maxn]of integer;
  a,b:array[1..maxn]of real;
  vis:array[1..maxn]of boolean;
  n,px,py,i,j,count:integer;
  t:real;
function next(x:byte):byte;
  begin
    if x=n then next:=1 else next:=x+1;
  end;
function sgn(x:longint):shortint;
  begin
    if x=0 then
      sgn:=0
    else if x>0 then
      sgn:=1
    else
      sgn:=-1;
  end;
function cross(xa,ya,xb,yb,xc,yc:integer):longint;
  var
    x1,y1,x2,y2:integer;
  begin
    x1:=xb-xa;y1:=yb-ya;
    x2:=xc-xa;y2:=yc-ya;
    cross:=x1*y2-x2*y1;
  end;
function dot(xa,ya,xb,yb,xc,yc:integer):longint;
  var
    x1,y1,x2,y2:integer;
  begin
    x1:=xb-xa;y1:=yb-ya;
    x2:=xc-xa;y2:=yc-ya;
    dot:=x1*x2+y1*y2;
  end;
function intersect(x1,y1,x2,y2,x3,y3,x4,y4:integer):boolean;
  begin
    intersect:=(sgn(cross(x1,y1,x2,y2,x3,y3))*sgn(cross(x1,y1,x2,y2,x4,y4))<0)
           and (sgn(cross(x3,y3,x4,y4,x1,y1))*sgn(cross(x3,y3,x4,y4,x2,y2))<0);
  end;
function dist(x1,y1,x2,y2:real):real;
  begin
    dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
  end;
function anycross:boolean;
  var
    i,j:byte;
  begin
    for i:=1 to n-2 do
      for j:=i+2 to n do
        if intersect(x[i],y[i],x[next(i)],y[next(i)],x[j],y[j],x[next(j)],y[next(j)]) then begin
          anycross:=true;exit;
        end;
    anycross:=false;
  end;
function angle(x1,y1,x2,y2:integer):real;
  var
    t:real;
  begin
    if x1=x2 then
      if y2>y1 then angle:=pi/2 else angle:=pi*3/2
    else begin
      t:=arctan((y2-y1)/(x2-x1));
      if x2<x1 then angle:=t+pi else if y2<y1 then angle:=t+pi*2 else angle:=t;
    end;
  end;
procedure look(angle:real);
  var
    i,v:byte;
    x1,y1,x2,y2,alpha,beta,d,min,t:real;
  begin
    min:=1e38;
    for i:=1 to n do begin
      if cross(px,py,x[i],y[i],x[next(i)],y[next(i)])>0 then begin
        x1:=x[i];y1:=y[i];x2:=x[next(i)];y2:=y[next(i)];alpha:=a[i];beta:=a[next(i)];
      end
      else begin
        x1:=x[next(i)];y1:=y[next(i)];x2:=x[i];y2:=y[i];alpha:=a[next(i)];beta:=a[i];
      end;
      if (sin(angle-alpha)>0) and (sin(beta-angle)>0) then begin
        t:=sin(angle-alpha)/sin(beta-angle)*dist(px,py,x1,y1)/dist(px,py,x2,y2);
        d:=dist(px,py,(x1+x2*t)/(1+t),(y1+y2*t)/(1+t));
        if d<min then begin
          min:=d;v:=i;
        end;
      end;
    end;
    if min<1e38 then vis[v]:=true;
  end;
begin
  assign(fin,'fence4.in');
  reset(fin);
  read(fin,n,px,py);
  for i:=1 to n do
    read(fin,x[i],y[i]);
  close(fin);

  assign(fout,'fence4.out');
  rewrite(fout);
  if anycross then
    writeln(fout,'NOFENCE')
  else begin
    for i:=1 to n do a[i]:=angle(px,py,x[i],y[i]);
    b:=a;for i:=1 to n-1 do for j:=i+1 to n do if b[i]>b[j] then begin t:=b[i];b[i]:=b[j];b[j]:=t;end;

    fillchar(vis,sizeof(vis),0);
    for i:=2 to n do if b[i]-b[i-1]>zero then look((b[i-1]+b[i])/2);
    t:=(b[n]+b[1]-pi*2)/2;if t<0 then look(t+pi*2) else look(t);

    count:=0;for i:=1 to n do if vis[i] then inc(count);
    writeln(fout,count);
    for i:=1 to n-2 do if vis[i] then writeln(fout,x[i],' ',y[i],' ',x[i+1],' ',y[i+1]);
    if vis[n] then writeln(fout,x[1],' ',y[1],' ',x[n],' ',y[n]);
    if vis[n-1] then writeln(fout,x[n-1],' ',y[n-1],' ',x[n],' ',y[n]);
  end;
  close(fout);
end.