Pagini recente » Cod sursa (job #2731940) | Profil FlorinHaja | Cod sursa (job #709569)
Cod sursa(job #709569)
#include<stdio.h>
#include<algorithm>
#define val 120010
using namespace std;
int i , n , punct_initial,D[val],u;
double x_min,y_min;
struct coordonate{
double x;
double y;
}S[val],aux;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int cmp(coordonate a, coordonate b){
return a.y*b.x<b.y*a.x;
}
int unghi(int a , int b , int c){
return (S[a].x*(S[b].y-S[c].y)+S[b].x*(S[c].y-S[a].y)+S[c].x*(S[a].y-S[b].y));
}
int main(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf %lf",&S[i].x,&S[i].y);
punct_initial=1;
for(i=1;i<=n;i++)
if((S[i].y<S[punct_initial].y)||(S[i].y==S[punct_initial].y&&S[i].x<S[punct_initial].x))
punct_initial=i;
x_min=S[punct_initial].x;
y_min=S[punct_initial].y;
for(i=1;i<=n;i++){
S[i].x-=x_min;
S[i].y-=y_min;
}
aux=S[1];
S[1]=S[punct_initial];
S[punct_initial]=aux;
sort(S+2,S+n+1,cmp);
D[1]=1;D[2]=2;u=2;
for(i=3;i<=n;i++){
while(unghi(D[u-1],D[u],i)<=0)
u--;
D[++u]=i;
}
fprintf(g,"%d\n",u);
for(i=1;i<=u;i++)
fprintf(g,"%lf %lf\n",S[D[i]].x+x_min,S[D[i]].y+y_min);
return 0;
}