Pagini recente » Cod sursa (job #603961) | Cod sursa (job #2493213) | Cod sursa (job #339258) | Cod sursa (job #845934) | Cod sursa (job #1110383)
#include<cstdio>
#include<algorithm>
using namespace std;
struct pct{
double x;
double y;
}v[150000];
int n,i,j,st[150000],nr,pmin;
double xmin,ymin,auxx,auxy;
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<0.000000000001)
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;
pmin=i;
}
else if(xmin==v[i].x&&v[i].y<v[pmin].y)
pmin=i;
}
auxx=v[1].x;
auxy=v[1].y;
v[1].x=v[pmin].x;
v[1].y=v[pmin].y;
v[pmin].x=auxx;
v[pmin].y=auxy;
sort(v+2,v+n+1,cmp);
st[1]=n;
st[2]=n-1;
nr=2;
for(i=n-2;i>=1;i--){
while(verif(v[st[nr-1]],v[st[nr]],v[i])==1&&nr>=1)
nr--;
st[++nr]=i;
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++){
fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
}
fclose(f);
fclose(g);
return 0;
}