Cod sursa(job #1920874)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 10 martie 2017 10:31:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define PII pair<double, double>

using namespace std;

int n, cnt;
PII p[125000];
PII S[125000];

double check(PII a, PII b, PII c)
{
    return 1.0 * ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y));
}

bool cmp(PII a, PII b)
{
    return (check(p[1], a, b) < 0);
}

int main(){
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
	sort(p+1, p+n+1);
	sort(p+2, p+n+1, cmp);
	S[1] = p[1];
	S[2] = p[2];
	cnt = 2;
	for (int i = 3; i <= n; i++)
	{
	    while (cnt >= 2 && check(S[cnt - 1], S[cnt], p[i]) > 0) --cnt;
	    S[++cnt] = p[i];
	}
	cout << cnt << "\n";
	cout << setprecision(6) << fixed;
	for (; cnt; cnt--)
	    cout << S[cnt].x << " " << S[cnt].y << "\n";
    cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}