Cod sursa(job #255276)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 8 februarie 2009 22:48:13
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

#ifdef __ACASA__
#define MAX 100
#else
#define MAX 124000
#endif



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;
}

int main() {
	// load
	freopen( "infasuratoare.in", "r", stdin );
	freopen( "infasuratoare.out", "w", stdout );
	scanf( "%d", &N );
	for ( i=0; i<N; ++i ) {
		scanf( "%lf %lf", &A[i].x, &A[i].y );
		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;
}