Pagini recente » Cod sursa (job #2367901) | Cod sursa (job #3258125) | Cod sursa (job #2556711) | Cod sursa (job #2813185) | Cod sursa (job #1117511)
#include<stdio.h>
#include<algorithm>
#define DIM 120005
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");
using namespace std;
struct punct{
double x, y;
} v[DIM];
long int n, st[DIM], Hst;
void citire(){
long int i, imin=1;
fscanf(f,"%ld\n",&n);
for(i=1;i<=n;i++){
fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);
if( v[i].x < v[imin].x || ( v[i].x == v[imin].x && v[i].y < v[imin].y ) ) imin=i;
}
swap( v[imin], v[1] ); // nu sunt singur ca merge cand imin=1
}
bool arie( punct A, punct B, punct 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
}
bool cmp( punct K1, punct K2 ){ return arie(v[1],K1,K2); }
void rezolvare(){
long int i;
st[1]=1; st[2]=2; Hst=2;
for(i=3;i<=n;i++){
while( !arie( v[st[Hst-1]], v[st[Hst]], v[i] ) && Hst>=2 ) Hst--;
st[++Hst]=i;
}
}
void afisare(){
long int i;
fprintf(g,"%ld\n",Hst);
for(i=Hst;i>=1;i--)
fprintf(g,"%.6llf %.6llf\n",v[ st[i] ].x,v[ st[i] ].y);
}
int main(){
citire();
sort(v+2,v+n+1,cmp);
rezolvare();
afisare();
return 0;
}