Cod sursa(job #2579902)

Utilizator Arteni_CristiArteni Cristi Arteni_Cristi Data 13 martie 2020 00:04:09
Problema Infasuratoare convexa Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.91 kb
uses math;
type date=record ax,ay,w:real end;
var t,v:array[1..120005] of date;
    n,i,j,k,poz:longint;
    d1,d2,x,y,a,b:real;
    aux:date;
begin
assign(input,'infasuratore.in'); reset(input);
assign(output,'infasuratoare.out'); rewrite(output);
readln(n);
for i:=1 to n do
 begin
  readln(v[i].ax,v[i].ay);
  if i=1 then
   begin
    x:=v[i].ax;
    y:=v[i].ay;
    poz:=i
   end else
  if (v[i].ay<y) or ((v[i].ay=y) and (v[i].ax<x)) then
   begin
    x:=v[i].ax;
    y:=v[i].ay;
    poz:=i
   end
 end;
for i:=1 to n do if i<>poz then
 begin
  d1:=sqrt(sqr(v[i].ax-x)+sqr(v[i].ay-y));
  d2:=v[i].ax-x;
  v[i].w:=d2/d1;
  v[i].w:=arccos(v[i].w)
 end;
for i:=1 to n-1 do
 for j:=1 to n-i do
  if (v[j].w>v[j+1].w) or ((v[j].w=v[j+1].w) and (v[j].ay>v[j+1].ay)) or
   ((v[j].w=v[j+1].w) and (v[j].ay=v[j+1].ay) and (v[j].ax>v[j+1].ax)) then
    begin
     aux:=v[j];
     v[j]:=v[j+1];
     v[j+1]:=aux
    end;
t[1].ax:=v[1].ax; t[1].ay:=v[1].ay;
t[2].ax:=v[2].ax; t[2].ay:=v[2].ay;
k:=2;
if n>=3 then
 begin
  t[3].ax:=v[3].ax;
  t[3].ay:=v[3].ay;
  j:=3; k:=3;
  while j<n do
   begin
    //determinant
    if t[k-2].ax*t[k-1].ay+t[k-2].ay*t[k].ax+t[k-1].ax*t[k].ay
     -t[k].ax*t[k-1].ay-t[k].ay*t[k-2].ax-t[k-1].ax*t[k-2].ay>=0 then
      begin
       inc(j); inc(k);
       t[k]:=v[j]
      end
     else
      begin
       t[k-1]:=t[k];
       dec(k)
      end
   end;
  if t[k-2].ax*t[k-1].ay+t[k-2].ay*t[k].ax+t[k-1].ax*t[k].ay
   -t[k].ax*t[k-1].ay-t[k].ay*t[k-2].ax-t[k-1].ax*t[k-2].ay<0 then
    begin
     t[k-1].ax:=t[k].ax;
     t[k-1].ay:=t[k].ay;
     dec(k)
    end
 end;
a:=t[k].ax;
b:=t[k].ay;
j:=n;
while (j>=1) and (v[j].w=t[k].w) do
 begin
  if (v[j].ax<>a) or (v[j].ay<>b) then
   begin
    inc(k);
    t[k]:=v[j]
   end;
  dec(j)
 end;
writeln(k);
for i:=1 to k do writeln(t[i].ax:6:6,' ',t[i].ay:6:6);
close(input);
close(output)
end.