Cod sursa(job #289816)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 martie 2009 00:30:50
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 100100

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct point { 
	double x, y;
	point( double _x, double _y ) { x = _x, y = _y; }
	point() {}
};
vector<point> V;
int M, N, i, j;

point ref;
bool operator<( const point& A, const point& B ) { 
	double Adx = A.x-ref.x, Ady = A.y-ref.y;
	double Bdx = B.x-ref.x, Bdy = B.y-ref.y;
	return Ady*Bdx < Adx*Bdy; 
}

void convex( vector<point> &A ) {
	int t=0, i;
	for ( i=1; i<N; ++i ) 
		if ( A[i].y < A[t].y || (A[i].y==A[t].y && A[i].x<A[t].x) ) 
			t = i;
	swap(A[0], A[t]);
	ref = A[0];
	sort(A.begin()+1, A.end()); 

	vector<point> r;
	r.push_back(A[0]);
	r.push_back(A[1]);
	r.push_back(A[2]);
	for ( i=3; i<N; ++i ) {
		while ( r.size()>=2 ) {
			ref = r[r.size()-2];
			if ( r[r.size()-1] < A[i] ) 
				break;
			r.pop_back();
		}
		r.push_back(A[i]);
	}
	A = r;
}

int main() {
	// load
	in >> N;
	for ( i=0; i<N; ++i ) {
		double x, y;
		in >> x >> y;
		V.push_back(point(x, y));
	}
	// magic stuff
	convex(V); 
	// write
	out << V.size() << "\n";
	out << setprecision(9);
	for ( i=0; i<(int)V.size(); ++i ) 
		out << V[i].x << " " << V[i].y << "\n";
	return 0;
}