Cod sursa(job #681168)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 16 februarie 2012 18:27:48
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<stdio.h>
#include<algorithm>

#define maxn 120005
#define INF (1<<30)
#define mp make_pair
#define eps (1e-12)

using namespace std;

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

int n,i,vf;

struct _point{
	double x,y;
	double ctg;
}A[maxn];
	
struct stiva{
	stiva(double first = 0,double second = 0):first(first),second(second){}
	
	double first;
	double second;
}St[maxn];
	
inline void swap ( _point &a , _point &b ){
	_point aux = a; a = b; b = aux;
}

inline bool equal ( double a , double b ){
	double dif = a - b;
	if ( dif < 0 )	dif = -dif;
	
	if ( dif < eps )	return 1;
	return 0;
}

inline bool det ( double x1 , double y1 , double x2 , double y2 , double x3 , double y3 ){
	double d = x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;
	if ( d >= 0 || equal(d,0) ){
		return 1;
	}
	return 0;
}

struct cmp{
	inline bool operator () ( const _point &a , const _point &b ){
		return a.ctg > b.ctg;
	}
};

int main () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
	}
	
	double ymin = INF,xmin; int poz;
	for ( i = 1 ; i <= n ; ++i ){
		if ( A[i].y < ymin ){
			ymin = A[i].y; xmin = A[i].x;
			poz = i;
		}
	}
	
	swap(A[1],A[poz]);
	for ( i = 1 ; i <= n ; ++i ){
		A[i].x -= xmin; A[i].y -= ymin;
		if ( i != 1 ){
			A[i].ctg = A[i].x / A[i].y;
		}
	}
	A[++n] = A[1];
	
	sort(A+2,A+n,cmp());
	
	for ( i = 1 ; i <= n ; ++i ){
		
		while ( vf > 1 && det(A[i].x,A[i].y,St[vf].first,St[vf].second,St[vf-1].first,St[vf-1].second) ){
			St[vf] = stiva(0.0,0.0);
			--vf;
		}
		St[++vf] = stiva(A[i].x,A[i].y);
	}
	
	fprintf(g,"%d\n",vf-1);
	for ( i = 1 ; i < vf ; ++i ){
		fprintf(g,"%lf %lf\n",St[i].first+xmin,St[i].second+ymin);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}