Pagini recente » Cod sursa (job #1380893) | Cod sursa (job #1610463) | Cod sursa (job #1642488) | Cod sursa (job #1307808) | Cod sursa (job #544833)
Cod sursa(job #544833)
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
double minx,miny;
int n,j,i,poz,stv[120001],k;
struct punct{
double x;
double y;
double ctg;
} v[120001];
int cmp(punct a,punct b){
return a.ctg>b.ctg;
}
int ver(int i1,int i2,int i3){
if(v[i2].x*v[i3].y+v[i1].x*v[i2].y+v[i3].x*v[i1].y>v[i2].x*v[i1].y+v[i1].x*v[i3].y+v[i3].x*v[i2].y)
return 1;
else
return 0;
}
int main() {
fscanf(f,"%d",&n);
miny=1000000000;
for(i=1;i<=n;++i){
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
if(miny>v[i].y){
miny=v[i].y;
minx=v[i].x;
poz=i;
}
}
v[poz].x=v[1].x;
v[poz].y=v[1].y;
v[1].x=v[1].y=0;
v[1].ctg=0;
for(i=2;i<=n;++i){
v[i].x-=minx;
v[i].y-=miny;
v[i].ctg=v[i].x/v[i].y;
}
sort(v+2,v+n+1,cmp);
stv[1]=1;
stv[2]=2;
k=2;
for(i=3;i<=n;++i){
while(!ver(stv[k-1],stv[k],i) && k>=2){
k--;
}
stv[++k]=i;
}
fprintf(g,"%d\n",k);
for(i=1;i<=k;++i)
fprintf(g,"%lf %lf\n",v[stv[i]].x+minx,v[stv[i]].y+miny);
fclose(g);
fclose(f);
return 0;
}