Cod sursa(job #1920864)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 10 martie 2017 10:28:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);
#define tie cin.tie(0);
#define mp make_pair
#define pb push_back
#define ll long long
#define x first
#define y second
#define PII pair<double, double>
#define PLL pair<ll, ll>
#define zeros(x) ( (x ^ (x - 1)) & x )
#define INF 0x3f3f3f3f
    
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(){
	IOS tie
	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 << 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;
}