Pagini recente » Cod sursa (job #3233333) | Cod sursa (job #2845603) | Cod sursa (job #1791910) | Cod sursa (job #1357143) | Cod sursa (job #709427)
Cod sursa(job #709427)
#include<stdio.h>
#include<algorithm>
#define val 120010
using namespace std;
int i , n , punct_initial,D[val],u;
float x_min,y_min;
struct coordonate{
float x;
float y;
}S[val];
const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";
FILE*f=fopen(InFile,"r");
FILE*g=fopen(OutFile,"w");
int cmp(coordonate a, coordonate b){
return a.y*b.x<b.y*a.x;
}
float 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))/2;
}
int main(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%f %f",&S[i].x,&S[i].y);
punct_initial=1;
for(i=1;i<=n;i++){
if(i==punct_initial)
continue;
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;
}
sort(S+1,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,"%f %f\n",S[D[i]].x+x_min,S[D[i]].y+y_min);
return 0;
}