Cod sursa(job #530557)

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

int i , j , n , m , ind[maxn] , cnt , first;
double minY = 1000000001 , minX;

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

bool cmp ( int i , int j) {
	return ((p[i].x - p[first].x) * (p[j].y - p[first].y) < (p[j].x - p[first].x) * (p[i].y - p[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 = i;
			minY = p[i].y;
			minX = p[i].x;
		}
	}
	
	for( i = 1 ; i <= n ; ++i ) 
		if ( p[i].x != p[first].x || p[i].y != p[first].y ) 
			ind[++cnt] = i;
	
	sort(ind + 1, ind + cnt + 1, cmp);
	vector < int > S;
	S.push_back(first);
	//S.push_back(p[2]);
	//S.push_back(p[3]);
	
	for( i = 1; i <= cnt ; ++i ) {
			for( ;S.size() >= 2 && rotateLeft(p[S[S.size() - 2]] , p[S[S.size() - 1]] , p[ind[i]]) > 0 ; )
				S.pop_back();
			S.push_back(ind[i]);
	}
	
	printf("%d\n",S.size());
	
	printf("%lf %lf\n",p[first].x,p[first].y);
	for(i = S.size() - 1; i >= 1 ; --i ) 
		printf("%lf %lf\n",p[S[i]].x,p[S[i]].y);
	
	
return 0;
}