Pagini recente » Cod sursa (job #1607601) | Cod sursa (job #2327226) | Cod sursa (job #1717314) | Cod sursa (job #2468428) | Cod sursa (job #616245)
Cod sursa(job #616245)
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=120001;
struct punct{
double x,y;
}x[N],y[N],z[N];
bool comp(punct a,punct b){
return a.x<b.x;
}
int n,nr1,nr2;
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
scanf("%lf%lf",&x[i].x,&x[i].y);
}
sort(&x[1],&x[n+1],comp);
y[++nr1]=x[1];
for(i=2;i<=n;i++){
while(nr1>1 && (x[i].y - y[nr1].y) * (x[i].x - y[nr1-1].x) <= (x[i].x - y[nr1].x) * (x[i].y - y[nr1-1].y))
--nr1;
y[++nr1]=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",nr1+nr2-2);
for(i=1;i<=nr1;++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;
}