Pagini recente » Istoria paginii runda/zxzx/clasament | Cod sursa (job #1511302) | Istoria paginii runda/denisilie94 | Istoria paginii runda/rar14/clasament | Cod sursa (job #1489210)
#include<cstdio>
#include<algorithm>
#define eps 0.00000001
using namespace std;
struct pct{
double x;
double y;
}v[130100],aux;
int n,i,j,nr,p,s[130100];
double xmin,ymin,xa,ya;
FILE *f,*g;
int verif(pct a,pct b,pct c){
double x=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
if(x<eps)
return 1;
return 0;
}
int cmp(pct a,pct b){
return verif(a,b,v[1]);
}
int main(){
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
fscanf(f,"%d",&n);
xmin=ymin=1000000000;
for(i=1;i<=n;i++){
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<xmin){
xmin=v[i].x;
p=i;
}
else if(v[i].x==xmin&&v[i].y<v[p].y)
p=i;
}
aux=v[1];
v[1]=v[p];
v[p]=aux;
sort(v+2,v+n+1,cmp);
s[1]=n;
s[2]=n-1;
nr=2;
for(i=n-2;i>=1;i--){
while( verif( v[ s[nr-1] ] , v[ s[nr] ] , v[i] ) )
nr--;
s[++nr]=i;
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++){
fprintf(g,"%.6lf %.6lf\n",v[ s[i] ].x,v[ s[i] ].y);
}
fclose(f);
fclose(g);
return 0;
}