Pagini recente » Borderou de evaluare (job #642010) | Cod sursa (job #2773597) | Cod sursa (job #70493) | Cod sursa (job #2588103) | Cod sursa (job #600600)
Cod sursa(job #600600)
#include<stdio.h>
#include<algorithm>
#define N 120001
using namespace std;
struct punct {
double x,y;
};
int n,nr;
punct x[N],y[N];
bool ver[N];
bool cmp(punct a,punct b) {
return a.x<b.x;
}
int main() {
int i,nrmax,ve;
punct smax;
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];
while(1) {
ve=0;
for(i=1;i<=n;++i) if(!ver[i]) {
if(nr==1 && i==1)
continue;
if(ve==0 || (y[nr].y - x[i].y) * (y[nr].x - smax.x) > (y[nr].y - smax.y) * (y[nr].x - x[i].x)) {
ve=1;
smax=x[i]; nrmax=i;
}
}
if(nrmax==1)
break;
y[++nr]=smax;
ver[nrmax]=1;
}
printf("%d\n",nr);
for(i=1;i<=nr;++i)
printf("%.6lf %.6lf\n",y[i].x,y[i].y);
return 0;
}