Cod sursa(job #530452)

Utilizator klamathixMihai Calancea klamathix Data 7 februarie 2011 20:05:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 130000;
ifstream fin("infasuratoare.in");

int i , j , n , m;
double minY = 1000000001 , minX;

struct point {
	double x , y;
}first , p[maxn];

bool cmp (point A, point B) {
	return (A.x - first.x) * (B.y - first.y) < (B.x - first.x) * (A.y - first.y);
}

bool rotateLeft ( point A , point B , point C ) {
	
	double det = A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x;
	return ( det > 0 );
}

int main()
{
	freopen("infasuratoare.out","w",stdout);
	
	fin >> n;
	for( i = 1 ; i <= n ; ++i ) {
		fin >> p[i].x >> p[i].y;
		if( p[i].y < minY || (p[i].y == minY && p[i].x < minX )) { 
			first = p[i];
			minY = p[i].y;
			minX = p[i].x;
		}
	}
	
	sort(p + 1, p + n + 1, cmp);
	
	vector <point> S;
	S.push_back(first);
	S.push_back(p[n]);
	S.push_back(p[n - 1]);
	
	for( i = n - 2; i >= 2 ; --i ) {
			for( ; rotateLeft(S[S.size() - 1] , S[S.size() - 2] , p[i]) ; )
				S.pop_back();
			S.push_back(p[i]);
	}
	
	printf("%d\n",S.size());
	
	for(i = 0 ; i < S.size() ; ++i ) 
		printf("%lf %lf\n",S[i].x,S[i].y);
	
	
return 0;
}