Cod sursa(job #1398110)

Utilizator howsiweiHow Si Wei howsiwei Data 23 martie 2015 23:34:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
typedef tuple<double,double> point;

bool ccw(point a, point b, point c)
{
	return (get<0>(b)-get<0>(a))*(get<1>(c)-get<1>(b))
		> (get<1>(b)-get<1>(a))*(get<0>(c)-get<0>(b));
}

vector<int> getcvh(const vector<point>& pts)
{
	int n = pts.size();
	vector<int> cvh(n);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		while (cnt >= 2 && !ccw(pts[cvh[cnt-2]], pts[cvh[cnt-1]], pts[i])) {
			cnt--;
		}
		cvh[cnt++] = i;
	}
	int lcnt = cnt-1;
	for (int i = n-1; i >= 0; i--) {
		while (cnt >= lcnt+2 && !ccw(pts[cvh[cnt-2]], pts[cvh[cnt-1]], pts[i])) {
			cnt--;
		}
		cvh[cnt++] = i;
	}
	cnt--;
	cvh.resize(cnt);
	return cvh;
}

int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	vector<point> pts(n);
	for (int i = 0; i < n; i++) {
		cin >> get<0>(pts[i]) >> get<1>(pts[i]);
	}
	sort(pts.begin(), pts.end());
	auto cvh = getcvh(pts);
	printf("%d\n", cvh.size());
	for (int i: cvh) {
		printf("%.6f %.6f\n", get<0>(pts[i]), get<1>(pts[i]));
	}
}