Pagini recente » Cod sursa (job #853543) | Cod sursa (job #579216) | Cod sursa (job #1736401) | Cod sursa (job #1258696) | Cod sursa (job #1003745)
#include <fstream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
FILE *g=fopen("infasuratoare.out","w");
int n,S[120010];
struct puncte{
double x,y,ctg;
};
puncte v[120010],t,ct;
long double det(puncte x,puncte y,puncte z){
return ((long double)x.x*y.y+y.x*z.y+z.x*x.y-z.x*y.y-y.x*x.y-x.x*z.y);
}
int cmp(puncte a,puncte b){
return (a.ctg>b.ctg);
}
int main(void){
register int i,j,p=0,k,q=0;
f>>n;
v[0].x=INT_MAX,v[0].y=INT_MAX;
for(i=1;i<=n;i++){
f>>v[i].x>>v[i].y;
if(v[i].y<v[p].y ||(v[i].y==v[p].y && v[i].x<v[p].x))
p=i;
}
ct=v[p];
v[p]=v[1],v[1]=ct;
v[1].x=0,v[1].y=0;
for(i=2;i<=n;i++){
v[i].x-=ct.x;
v[i].y-=ct.y;
v[i].ctg=(v[i].y==0?INT_MAX:(v[i].x/v[i].y));
}
sort(v+2,v+n+1,cmp);
S[1]=1,S[2]=2,k=2;
for(i=3;i<=n;i++){
while(k>=2 && det(v[S[k-1]],v[S[k]],v[i])<=0)
k--;
S[++k]=i;
}
fprintf(g,"%d\n",k);
for(i=1;i<=k;i++){
fprintf(g,"%.6f %.6f\n",v[S[i]].x+ct.x,v[S[i]].y+ct.y);
}
f.close();
fclose(g);
return 0;
}