Cod sursa(job #2267843)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 24 octombrie 2018 09:00:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define ll long long
#define pdd pair < double, double >
 
using namespace std;
 
int n, vf;
pdd a[125100], st[125100];
 
double 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 << setprecision(6) << fixed;
	for (; vf; vf--){
		cout << st[vf].first << " " << st[vf].second << "\n";
	}
 
    return 0;
}