Pagini recente » Cod sursa (job #2475330) | Cod sursa (job #613588) | Cod sursa (job #2958975) | Cod sursa (job #1661399) | Cod sursa (job #739023)
Cod sursa(job #739023)
#include <cstdio>
#include <algorithm>
#define MAX 120001
#define EPS 1e-12
using namespace std;
struct point{ long double x,y; }p[MAX],sus[MAX],jos[MAX],c[MAX];
int n,n1,n2,k;
inline long double det(point p1,point p2,point p3){
return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p3.x*p2.y-p1.x*p3.y-p2.x*p1.y;
}
inline bool cmp(point p1,point p2){ return p2.x-p1.x>EPS; }
void desp(){
int p1=1,p2=1;
for(int i=1;i<=n;i++){
if(p[p1].x-p[i].x>EPS)p1=i;
if(p[i].x-p[p2].x>EPS)p2=i; }
sus[++n1]=p[p1];
jos[++n2]=p[p1];
for(int i=1;i<=n;i++)
if(i!=p1&&i!=p2)
if(det(p[p1],p[p2],p[i])>0)sus[++n1]=p[i]; else
if(det(p[p1],p[p2],p[i])<0)jos[++n2]=p[i];
sus[++n1]=p[p2];
jos[++n2]=p[p2];
}
void make_sus(){
c[1]=sus[1]; c[2]=sus[2]; k=2;
for(int i=3;i<=n1;i++){
while(k>=2&&det(c[k-1],c[k],sus[i])+EPS>0)k--;
c[++k]=sus[i];
}
for(int i=1;i<=k;i++)sus[i]=c[i];
n1=k;
}
void make_jos(){
c[1]=jos[1]; c[2]=jos[2]; k=2;
for(int i=3;i<=n2;i++){
while(k>=2&&det(c[k-1],c[k],jos[i])-EPS<0)k--;
c[++k]=jos[i];
}
for(int i=1;i<=k;i++)jos[i]=c[i];
n2=k;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%llf %llf",&p[i].x,&p[i].y);
desp();
sort(sus+1,sus+n1+1,cmp);
sort(jos+1,jos+n2+1,cmp);
make_sus();
make_jos();
printf("%d\n",n1+n2-2);
for(int i=1;i<=n2;i++)printf("%llf %llf\n",jos[i].x,jos[i].y);
for(int i=n1-1;i>1;i--)printf("%llf %llf\n",sus[i].x,sus[i].y);
}