Cod sursa(job #2410220)

Utilizator LucaSeriSeritan Luca LucaSeri Data 19 aprilie 2019 20:15:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
 
using namespace std;

const int MAXN = 1e5 + 2e4 + 10;

struct p{
	long double x, y;
	p(long double _x = 0, long double _y = 0) : x(_x), y(_y) {}

	const bool operator < (const p &o) const {
		if(x == o.x) return y < o.y;
		return x < o.x;
	}
}v[MAXN], stk[MAXN];

int stkSize = 0;

long double det(p a, p b, p c) {
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("infasuratoare.in", "r", stdin);
		freopen("infasuratoare.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> v[i].x >> v[i].y;
		if(v[i] < v[0]) swap(v[i], v[0]);
	}

	sort(v + 1, v + n, [&](p &a, p &b) -> bool {
		return det(v[0], a, b) < 0;
	});

	v[n] = v[0];
	stkSize = 0;
	for(int i = 0; i <= n; ++i) {
		while(stkSize >= 2 && det(stk[stkSize-1], stk[stkSize], v[i]) >= 0) {
			stkSize --;
		}

		stk[++stkSize] = v[i];
	} 

	cout << stkSize - 1 << '\n';
	for(int i = 1; i <= stkSize - 1; ++i) {
		cout << setprecision(12) << fixed << stk[i].x << ' ' << stk[i].y << '\n';
	}
	return 0;
}