Pagini recente » Cod sursa (job #2834781) | Cod sursa (job #1470154) | Cod sursa (job #3158555) | Cod sursa (job #3284086) | Cod sursa (job #544887)
Cod sursa(job #544887)
#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 P1,int P2,int P3){
long double A, X1, Y1, X2, Y2, X3, Y3;
X1 = v[P1].x, Y1 = v[P1].y, X2 = v[P2].x, Y2 = v[P2].y, X3 = v[P3].x, Y3 = v[P3].y;
A = (X3 - X2) * (Y1 - Y2) - (X1 - X2) * (Y3 - Y2);
if (A > 0)
return 1;
return 0;
/*
if(v[i2].x*(long double)v[i3].y+v[i1].x*(long double)v[i2].y+v[i3].x*(long double)v[i1].y
>(long double)v[i2].x*v[i1].y+(long double)v[i1].x*v[i3].y+(long double)v[i3].x*v[i2].y)
return 1;
else
return 0;
*/
}
int main() {
fscanf(f,"%d",&n);
miny=1LL<<62;
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;
}