Pagini recente » Cod sursa (job #1354890) | Statistici roma gia (romagia) | Istoria paginii grigore-moisil-2018/clasament/11-12 | Istoria paginii runda/simulare_oji_05_03_2023 | Cod sursa (job #1659987)
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.