Cod sursa(job #1556549)

Utilizator howsiweiHow Si Wei howsiwei Data 25 decembrie 2015 11:39:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;
typedef complex<double> Point;
typedef complex<double> Vec;

bool cmp(Point a, Point 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(Point a, Point b, Point c) {
	return cross(b-a, c-b) > 0;
}

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++) {
		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]));
	}
}