Pagini recente » Cod sursa (job #2321227) | Cod sursa (job #2715285) | Cod sursa (job #1196991) | Cod sursa (job #2282827) | Cod sursa (job #1003265)
#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,tg;
};
puncte v[120010],t,ct;
int cmp(puncte a,puncte b){
return (a.tg<b.tg);
}
double det(int x,int y,int z){
return (v[x].x*v[y].y+v[y].x*v[z].y+v[z].x*v[x].y-v[z].x*v[y].y-v[y].x*v[x].y-v[x].x*v[z].y);
}
int main(void){
register int i,j,p=1;
f>>n;
for(i=1;i<=n;i++){
f>>v[i].x>>v[i].y;
if(v[i].y<v[p].y)
p=i;
}
t=v[p],v[p]=v[1],v[1]=t;
for(i=2;i<=n;i++){
v[i].y=v[i].y-v[1].y;
v[i].x=v[i].x-v[1].x;
v[i].tg=(v[i].x!=0?v[i].y/v[i].x:INT_MAX);
}
ct=v[1],v[1].y=0,v[1].x=0;
sort(v+2,v+n+1,cmp);
p=2;
while(v[p].tg<0)
p++;
S[1]=1,S[2]=p,S[0]=2;
for(i=p+1;i<=n;i++){
while(S[0]>=2 && det(S[S[0]-1],S[S[0]],i)<0){
S[0]--;
}
S[++S[0]]=i;
}
for(i=2;i<p;i++){
while(S[0]>=2 && det(S[S[0]-1],S[S[0]],i)<0){
S[0]--;
}
S[++S[0]]=i;
}
fprintf(g,"%d\n",S[0]);
for(i=1;i<=S[0];i++){
fprintf(g,"%.6f %.6f\n",v[S[i]].x+ct.x,v[S[i]].y+ct.y);
}
f.close();
fclose(g);
return 0;
}