Pagini recente » Cod sursa (job #2326944) | Cod sursa (job #42418) | Cod sursa (job #750461) | Cod sursa (job #2174346) | Cod sursa (job #1377702)
#include<stdio.h>
#include<algorithm>
#define MAXN 120005
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");
using namespace std;
struct Puncte{ double x, y; } v[MAXN];
long int N;
long int ST[MAXN], HST;
bool Arie( Puncte A, Puncte B, Puncte C ){
double arie = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
if( arie > 0 ) return 0; // sens orar
return 1; // sens trigonometric
}
void Citire(){
long int i, imin;
Puncte minim;
fscanf(f,"%ld\n",&N);
for(i=1;i<=N;i++){
fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);
if(i==1){ imin = i; minim = v[i]; }
else if( v[i].x < minim.x || ( v[i].x == minim.x && v[i].y < minim.y ) ){
minim = v[i];
imin = i;
}
}
swap( v[1], v[imin] );
}
bool cmp( Puncte A, Puncte B ){ return Arie( v[1], A, B ); }
void Rezolvare(){
long int i;
ST[1]=1; ST[2]=2; HST=2;
for(i=3;i<=N;i++){
while( HST >= 2 && Arie( v[ST[HST-1]], v[ST[HST]], v[i] )==0 ) HST--;
ST[++HST] = i;
}
fprintf(g,"%ld\n",HST);
for(i=HST;i>=1;i--)
fprintf(g,"%.6lf %.6lf\n",v[ST[i]].x,v[ST[i]].y);
}
int main(){
Citire();
sort(v+2,v+N+1,cmp);
Rezolvare();
return 0;
}