Cod sursa(job #1365923)

Utilizator BLz0rDospra Cristian BLz0r Data 28 februarie 2015 16:54:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 120002

FILE *f = fopen ( "infasuratoare.in", "r" );
FILE *g = fopen ( "infasuratoare.out", "w" );

struct point{
	double x, y;
}v[Nmax], Q[Nmax];

int N, L;	

bool cmp ( point A, point B ){
	
	if ( A.x == B.x )
		return A.y < B.y; 
	
	return A.x < B.x;
}

double CrossProduct ( point A, point B, point C ){
	return A.x * ( B.y - C.y ) + B.x * ( C.y - A.y ) + C.x * ( A.y - B.y ); 
}
	
void ConvexHull (){
	
	for ( int i = 1; i <= N; ++i ){
		while ( L > 1 && CrossProduct ( Q[L-1], Q[L], v[i] ) <= 0 )
			L--;
		Q[++L] = v[i];
	}
	int l = L;
	
	for ( int i = N; i >= 1; --i ){
		while ( L > l &&  CrossProduct ( Q[L-1], Q[L], v[i] ) <= 0 )
			L--;
		Q[++L] = v[i];
	}
	L--;
}

int main(){
	
	fscanf ( f, "%d", &N );
	
	for ( int i = 1; i <= N; ++i )
		fscanf ( f, "%lf%lf", &v[i].x, &v[i].y );
	
	sort ( v + 1, v + N + 1, cmp );
	
	ConvexHull ();
	
	fprintf ( g, "%d\n", L );
	for ( int i = 1; i <= L; ++i )
		fprintf ( g, "%lf %lf\n", Q[i].x, Q[i].y );
	
	return 0;
}