Cod sursa(job #1659987)

Utilizator laura.calimanLaura Caliman laura.caliman Data 22 martie 2016 18:59:13
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.78 kb
var n,i,j,k:longint;
    xm,ym:real;
    a:array[1..120000] of longint;
    x,y,cos:array[1..120000] of real;
    
procedure sw(var a,b:real);
var c:real;
begin
  c:=a;
  a:=b;
  b:=c;
end;

procedure qs(st,dr:longint);
var i,j:longint;
    m:real;
begin
  i:=st; j:=dr;
  m:=cos[(i+j) div 2];
  while i<j do begin
    while cos[i]<m do inc(i);
    while cos[j]>m do dec(j);
    if i<=j then begin
      sw(cos[i],cos[j]);
      sw(x[i],x[j]);
      sw(y[i],y[j]);
      inc(i);
      dec(j);
    end;
  end;
  if i<dr then qs(i,dr);
  if st<j then qs(st,j);
end;

procedure infas(g:longint);
var m:real; i,r,t:longint;
begin
  r:=k-1;
  t:=k;
//  writeln(a[r],' ',a[t],' ',g,' ',k);
  m:=(x[a[r]]*(y[a[t]]-y[g])+x[a[t]]*(y[g]-y[a[r]])+x[g]*(y[a[r]]-y[a[t]]));
//  writeln(m);
  if m>0 then
  begin
    inc(k);
    a[k]:=g;  
//    for i:=1 to n do write(a[i],' ');
//    writeln;
    if g<n then
      infas(g+1);
  end else begin
//    a[r]:=a[t];
//    a[t]:=a[g];
    dec(k);
    if r>1 then 
      infas(g);
  end;
end;
  
begin
  assign(input,'infasuratoare.in');
  assign(output,'infasuratoare.out');
  reset(input);
  rewrite(output);
  read(n);
  read(x[1],y[1]);
  xm:=x[1];
  ym:=y[1];
  for i:=2 to n do begin
    read(x[i],y[i]);
    if (y[i]=ym) and (x[i]<xm) then xm:=x[i];
    if y[i]<ym then begin
      ym:=y[i];
      xm:=x[i];
    end;
  end;
//  write(xm,' ',ym);
  for i:=1 to n do begin
    if (x[i]=xm) and (y[i]=ym) then cos[i]:=-1
    else cos[i]:=-(x[i]-xm)/sqrt(sqr(x[i]-xm)+sqr(y[i]-ym));
//    writeln(cos[i]);
  end;
  qs(1,n);
//  for i:=1 to n do
//    writeln(cos[i],' ',x[i],' ',y[i]);
  a[1]:=1;
  a[2]:=2;
  k:=2;
  infas(3);
  writeln(k);
  for i:=1 to k do writeln(x[a[i]],' ',y[a[i]]);
end.