Pagini recente » Cod sursa (job #2166686) | Borderou de evaluare (job #2013742) | Cod sursa (job #2421432) | Cod sursa (job #9173) | Cod sursa (job #600609)
Cod sursa(job #600609)
#include<stdio.h>
#include<algorithm>
#define N 120001
using namespace std;
struct punct {
double x,y;
};
int n,nr,nr2;
punct x[N],y[N],z[N];
bool ver[N];
bool cmp(punct a,punct b) {
return a.x<b.x;
}
int main() {
int i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&x[i].x,&x[i].y);
sort(&x[1],&x[n+1],cmp);
y[++nr]=x[1];
for(i=2;i<=n;++i) {
while(nr>1 && (x[i].y - y[nr].y) * (x[i].x - y[nr-1].x) <= (x[i].x - y[nr].x) * (x[i].y - y[nr-1].y))
--nr;
y[++nr]=x[i];
}
z[++nr2]=x[1];
for(i=2;i<=n;++i) {
while(nr2>1 && (x[i].y - z[nr2].y) * (x[i].x - z[nr2-1].x) >= (x[i].x - z[nr2].x) * (x[i].y - z[nr2-1].y))
--nr2;
z[++nr2]=x[i];
}
printf("%d\n",nr+nr2-2);
for(i=1;i<=nr;++i)
printf("%.6lf %.6lf\n",y[i].x,y[i].y);
for(i=nr2-1;i>1;--i)
printf("%.6lf %.6lf\n",z[i].x,z[i].y);
return 0;
}