Cod sursa(job #1668723)

Utilizator howsiweiHow Si Wei howsiwei Data 30 martie 2016 00:03:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;
typedef complex<double> Pnt;
typedef complex<double> Vec;

bool cmp(Pnt a, Pnt b) {
	return real(a) < real(b)
		|| real(a) == real(b) && imag(a) < imag(b);
}

double cross(Vec a, Vec b) {
	return imag(conj(a)*b);
}

bool ccw(Pnt a, Pnt b, Pnt c) {
	return cross(b-a, c-b) > 0;
}

vector<int> getcvh(const vector<Pnt>& pts) {
	int n = pts.size();
	if (pts.front() == pts.back()) return {0};
	vector<int> cvh;
	for (int i = 0; i < n; i++) {
		while (cvh.size() >= 2
			&& !ccw(pts[*(cvh.end()-2)], pts[*(cvh.end()-1)], pts[i]))
			cvh.pop_back();
		if (i != n-1) cvh.push_back(i);
	}
	// puts("b");
	auto lcnt = cvh.size();
	for (int i = n-1; i >= 0; i--) {
		while (cvh.size() >= lcnt+2
			&& !ccw(pts[*(cvh.end()-2)], pts[*(cvh.end()-1)], pts[i]))
			cvh.pop_back();
		if (i != 0) cvh.push_back(i);
	}
	// puts("c");
	return cvh;
}

int main() {
#ifdef INFOARENA
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<Pnt> pts(n);
	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;
		pts[i] = {x,y};
	}
	sort(pts.begin(), pts.end(), cmp);
	auto cvh = getcvh(pts);
	printf("%d\n", cvh.size());
	for (int i: cvh) {
		printf("%.6f %.6f\n", real(pts[i]), imag(pts[i]));
	}
}