Cod sursa(job #2238817)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 7 septembrie 2018 18:26:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <double, double> Point;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

double crossProduct (const Point &a, const Point &b, const Point &c) {
	return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); // mut punctele a.i. a sa fie in (0, 0)
}

const int NMAX = 12e4 + 5;
Point v[NMAX];
int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL_DEFINE
    freopen (".in", "r", stdin);
#endif
	g.precision (6);
	g << fixed;
	
	f >> n;
	for (int i = 1; i <= n; ++i) f >> v[i].fi >> v[i].se;
	
	int pos = 1;
	for (int i = 2; i <= n; ++i) {
		if (v[i] < v[pos]) {
			pos = i;	
		}
	}
	swap (v[1], v[pos]);
	
	sort (v + 2, v + 1 + n, [] (const Point &a, const Point &b) {
		return (crossProduct (v[1], a, b) < 0);
	});
	
	vi stk;
	int top = 1;
	stk.pb (1);
	stk.pb (2);
	
	for (int i = 3; i <= n; ++i) {
		while (top >= 1 && crossProduct (v[stk[top - 1]], v[i], v[stk[top]]) < 0) {
			--top;
			stk.pop_back();
		}
		stk.pb (i);
		++top;
	}
	
	g << top + 1 << '\n';

	reverse (all (stk));
	
	for (int &i : stk) {
		g << v[i].fi << ' ' << v[i].se << '\n';
	}
}