Cod sursa(job #409971)

Utilizator nickyyLal Daniel Emanuel nickyy Data 3 martie 2010 22:46:47
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.51 kb
const infile='infasuratoare.in';
  outfile='infasuratoare.out';
  maxn=120003;
var x,y:array[0..maxn]of real;
  p,S:array[0..maxn]of longint;
  n,vf,p0:longint;

 procedure citire;
 var i:longint;
 begin
   assign(input,infile); reset(input); readln(n);
   p0:=1;
   for i:=1 to n do begin
     readln(x[i],y[i]);
     if(y[i]<y[p0])or((y[i]=y[p0])and(x[i]<x[p0]))then p0:=i;
     end;
   close(input);
 end;

 procedure sort(st,dr:longint);
 var i,j,a:longint;
   xm,ym:real;
 begin
   i:=st; j:=dr; xm:=x[p[(i+j)div 2]]; ym:=y[p[(i+j)div 2]];
   while(i<=j)do begin
     while((x[p[j]]-x[p0])*(ym-y[p0]) < (xm-x[p0])*(y[p[j]]-y[p0]))do dec(j);
     while((x[p[i]]-x[p0])*(ym-y[p0]) > (xm-x[p0])*(y[p[i]]-y[p0]))do inc(i);
     if(i<=j)then begin
       a:=p[i]; p[i]:=p[j]; p[j]:=a;
       inc(i); dec(j);
       end;
     end;
   if(i<dr)then sort(i,dr);
   if(st<j)then sort(st,j);
 end;

 function det(p1,p2,p3:longint):real;
 begin
   det:=x[p1]*(y[p2]-y[p3])+x[p2]*(y[p3]-y[p1])+x[p3]*(y[p1]-y[p2]);
 end;

 procedure solve;
 var i:longint;
 begin
   for i:=1 to n do if(i<>p0)then begin inc(p[0]); p[p[0]]:=i; end;
   sort(1,p[0]);
   vf:=3;
   S[1]:=p0; S[2]:=p[1]; s[3]:=p[2];
   for i:=3 to p[0] do begin
     while(vf>2)and(det(S[vf-1],S[vf],p[i])<=0)do dec(vf);
     inc(vf); S[vf]:=p[i];
     end;
   assign(output,outfile); rewrite(output);
   writeln(vf);
   for i:=1 to vf do writeln(x[S[i]]:16:6,' ',y[S[i]]:16:6);
   close(output);
 end;

begin
  citire; solve;
end.