Pagini recente » Cod sursa (job #1096907) | Cod sursa (job #2246180) | Cod sursa (job #2254730) | Cod sursa (job #88476) | Cod sursa (job #709429)
Cod sursa(job #709429)
#include<stdio.h>
#include<algorithm>
using namespace std;
int i , q , S[120010],n,minim,u;
float x_min,y_min;
float d;
struct pereche{
float x;
float y;
}V[120010];
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
void read(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%f%f",&V[i].x,&V[i].y);
}
int cmp(pereche a, pereche b){
if(a.x*b.y<a.y*b.x)
return 0;
return 1;
}
float unghi(int a , int b , int c){
return (V[a].x*(V[b].y-V[c].y)+V[b].x*(V[c].y-V[a].y)+V[c].x*(V[a].y-V[b].y))/2;
}
int main(){
read();minim=1;
for(i=2;i<=n;i++){
if(V[i].y<V[minim].y)
minim=i;
else if(V[i].y==V[minim].y&&V[i].x<V[minim].x)
minim=i;
}
x_min=V[minim].x;y_min=V[minim].y;
for(i=1;i<=n;i++){
V[i].x-=x_min;
V[i].y-=y_min;
}
sort(V+2,V+n+1,cmp);
S[1]=1;S[2]=2;u=2;
for(i=3;i<=n;i++){
while(unghi(S[u-1],S[u],i)<=0)
u--;
S[++u]=i;
}
fprintf(g,"%d\n",u);
for(i=1;i<=u;i++)
fprintf(g,"%f %f\n",V[S[i]].x+x_min,V[S[i]].y+y_min);
return 0;
}