Pagini recente » Cod sursa (job #513534) | Cod sursa (job #403823) | Cod sursa (job #2781154) | Cod sursa (job #911449) | Cod sursa (job #545412)
Cod sursa(job #545412)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define Nmax 120005
#define Inf 1000000010
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int i,N,st,S[Nmax],pmin;
double ymin,xmin;
struct pct{
double x;
double y;
double ctg;
}A[Nmax];
int cmp( pct a, pct b ){
return a.ctg > b.ctg ;
}
int det(int a,int b,int c){
double aux = A[a].x * ( A[b].y - A[c].y ) + A[b].x * ( A[c].y - A[a].y ) + A[c].x * ( A[a].y - A[b].y ) ;
if ( aux > 0 )
return 1;
return 0;
}
int main () {
fscanf(f,"%d",&N);
xmin = ymin = Inf;
for ( i = 1 ; i <= N ; ++i ){
fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
if ( A[i].y < ymin ){
pmin = i;
ymin = A[i].y;
xmin = A[i].x;
}
}
pct aux = A[1];
A[1] = A[pmin];
A[pmin] = aux;
for ( i = 1 ; i <= N ; ++i ){
A[i].y -= ymin;
A[i].x -= xmin;
if (i!=1)
A[i].ctg = A[i].x/A[i].y;
}
sort(A+2,A+N+1,cmp);
S[++st] = 1; S[++st] = 2;
for ( i = 3 ; i <= N ; ++i ){
while ( !det( S[st-1], S[st],i ) && st > 2 )
--st;
S[++st] = i;
}
fprintf(g,"%d\n",st);
for ( i = 1 ; i <= st ; ++i ){
fprintf(g,"%lf %lf\n",A[S[i]].x+xmin,A[S[i]].y+ymin);
}
fclose(f);
fclose(g);
return 0;
}