Pagini recente » Cod sursa (job #2475982) | Cod sursa (job #978253) | Cod sursa (job #2089239) | Cod sursa (job #972532) | Cod sursa (job #2528027)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define db double
#define MAXN 120001
#define eps 1e-12
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct points{
db x,y;
}v[MAXN];
int st[MAXN];
bool ok[MAXN];
bool comp(points a,points b){
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int cmpl(db a,db b){
if(a+eps<b) return 1;
if(b+eps<a) return -1;
return 0;
}
int sign(points a,points b,points c){
db A,B,C;
A=a.y-b.y;
B=b.x-a.x;
C=a.x*b.y-b.x*a.y;
return cmpl(A*c.x+B*c.y+C,0);
}
int main(){
int n;
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,comp);
/*for(int i=1;i<=n;i++){
fout<<fixed;
fout<<setprecision(6);
fout<<v[i].x<<' '<<v[i].y<<'\n';
}*/
int nrst=0,ii,updown,h;
st[1]=1,st[2]=2;
ok[2]=1;
nrst=2;
ii=3;
updown=1;
while(!ok[1]){
while(ok[ii]){
if(ii==n) updown=-1;
ii+=updown;
}
while(nrst>=2 and sign(v[st[nrst-1]],v[st[nrst]],v[ii])==-1)
ok[st[nrst--]]=0;
nrst++;
st[nrst]=ii;
ok[ii]=1;
}
h=nrst-1;
fout<<h<<'\n';
for(int i=h+1;i>=2;i--){
fout<<fixed;
fout<<setprecision(6);
fout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}
return 0;
}