Cod sursa(job #530541)

Utilizator klamathixMihai Calancea klamathix Data 7 februarie 2011 22:28:25
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 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);
}

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

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[2]);
	S.push_back(p[3]);
	
	for( i = 4; i <= n ; ++i ) {
			for( ;S.size() >= 2 && rotateLeft(S[S.size() - 2] , S[S.size() - 1] , p[i]) > 0 ; )
				S.pop_back();
			S.push_back(p[i]);
	}
	
	printf("%d\n",S.size());
	
	printf("%lf %lf\n",first.x,first.y);
	for(i = S.size() - 1; i >= 1 ; --i ) 
		printf("%lf %lf\n",S[i].x,S[i].y);
	
	
return 0;
}