Cod sursa(job #545558)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 3 martie 2011 16:04:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxN 120005
#define Inf 1000000010
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");

int i,N,poz,S[maxN],st;
double ymin,xmin;

struct pct{
	double x;
	double y;
	double ctg;
}A[maxN];

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 ){
			ymin = A[i].y;
			xmin = A[i].x;
			poz = i;
		}
	}
	
	A[poz].x = A[poz].y = 0;
	pct aux = A[1];
	A[1] = A[poz];
	A[poz] = aux;
	
	for ( i = 2 ; i <= N ; ++i ){
		A[i].x -= xmin;
		A[i].y -= ymin;
		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;
}