Cod sursa(job #2267819)

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

using namespace std;

int n, vf, vf2;
pdd a[120100], st[120100], st2[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 cmp1(pdd a, pdd b, pdd c){
	return check(a, 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);

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

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

	st2[++vf2] = a[n];
	st2[++vf2] = a[n - 1];

	for (int i = n - 2; i; i--){
		while (vf2 >= 2 && cmp1(st2[vf2 - 1], st2[vf2], a[i])) --vf2;
		st2[++vf2] = a[i];
	}

	for (int i = 2; i < vf2; i++) st[++vf] = st2[i];

	cout << vf << "\n";
	cout << fixed << setprecision(10);

	for (int i = vf; i; i--) cout << st[i].first << " " << st[i].second << "\n"; 

    return 0;
}