Pagini recente » Cod sursa (job #2971555) | Cod sursa (job #1816862) | Cod sursa (job #1352462) | Cod sursa (job #2388283) | Cod sursa (job #255281)
Cod sursa(job #255281)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#ifdef __ACASA__
#define MAX 100
#else
#define MAX 124000
#endif
#define BMAX 500
struct point { double x, y; } A[MAX], mi;
int N, i, S[MAX], k;
int comp( point A, point B ) {
return atan2(A.y-mi.y,A.x-mi.x) < atan2(B.y-mi.y,B.x-mi.x);
}
int can_pop( int lvl, int i ) {
point P, Q;
P.x = A[i].x - A[S[lvl]].x;
P.y = A[i].y - A[S[lvl]].y;
Q.x = A[S[lvl]].x - A[S[lvl-1]].x;
Q.y = A[S[lvl]].y - A[S[lvl-1]].y;
double delta = Q.x * P.y - Q.y * P.x;
return delta < 0;
}
char buf[BMAX];
int parse() {
int ret = 0;
while ( buf[k]>='0' && buf[k]<='9' )
ret = ret*10 + buf[k++] - '0';
return ret;
}
int main() {
// load
freopen( "infasuratoare.in", "r", stdin );
freopen( "infasuratoare.out", "w", stdout );
scanf( "%d\n", &N );
for ( i=0; i<N; ++i ) {
fgets( buf, BMAX, stdin );
// scanf( "%lf %lf", &A[i].x, &A[i].y );
k = 0;
A[i].x = parse();
++k;
A[i].y = parse();
mi = i==0 ? A[i] : ( mi.y > A[i].y || (mi.y==A[i].y && mi.x > A[i].x) ? A[i] : mi );
}
sort( A, A+N, comp );
// solve
S[0] = 0, S[1] = 1, k = 2;
for ( i=2; i<N; ++i ) {
while ( k>1 && can_pop(k-1,i) ) --k;
S[ k++ ] = i;
}
printf( "%d\n", k );
for ( i=0; i<k; ++i )
printf( "%lf %lf\n", A[S[i]].x, A[S[i]].y );
return 0;
}