Cod sursa(job #937345)

Utilizator howsiweiHow Si Wei howsiwei Data 10 aprilie 2013 06:52:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<double,double> dd;
#define x first
#define y second
#define let(X, A) typeof(A) X(A)
#define ech(It, A) for (let( It, A.begin() ); It != A.end(); ++It)

bool ccw( dd a, dd b, dd c ) { // if collinear return false
	return (c.x-b.x) * (b.y-a.y) < (c.y-b.y) * (b.x-a.x);
}

int main() {
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");
	int n;
	fin >> n;
	vector<dd> P(n);
	for (int i=0; i<n; ++i) {
		fin >> P[i].first >> P[i].second;
	}
	sort( P.begin(), P.end() );
	vector<dd> hull(n);
	int cnt = 0;

	for (int i=0; i<n; ++i) {
		while (cnt > 1 && !ccw( hull[cnt-2], hull[cnt-1], P[i] ))
			--cnt;
		hull[cnt++] = P[i];
	}
	int dcnt = cnt;

	for (int i=n-2; i>=0; --i) {
		while (cnt > dcnt && !ccw( hull[cnt-2], hull[cnt-1], P[i] ))
			--cnt;
		hull[cnt++] = P[i];
	}

	hull.resize(--cnt);

	fout << hull.size() << '\n';
	fout.precision(6);
	ech( it, hull ) {
		fout << fixed << it->x << ' ' << it->y << '\n';
	}
	return 0;
}