Cod sursa(job #2267824)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 24 octombrie 2018 08:43:57
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
#define ll long long
#define pdd pair < double, double >

using namespace std;

int n, vf;
pdd a[120100], st[120100];

int check(pdd a, pdd b, pdd c){
	return 1.0 * ((b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second));
}

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
	cin >> n;
	for (int i = 1; i <= n; ++i){
		cin >> a[i].first >> a[i].second;
	}

	sort(a + 1, a + n + 1);
	sort(a + 2, a + n + 1, cmp);

	st[++vf] = a[1];
	st[++vf] = a[2];

	for (int i = 3; i <= n; i++){
		while (vf >= 2 && check(st[vf - 1], st[vf], a[i]) > 0) --vf;
		st[++vf] = a[i];
	}

	cout << vf << "\n";
	cout << fixed << setprecision(10);
	for (; vf; vf--){
		cout << st[vf].first << " " << st[vf].second << "\n";
	}

    return 0;
}