Cod sursa(job #1731851)

Utilizator mikeshadowIon Complot mikeshadow Data 20 iulie 2016 06:48:27
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#define all(x) x.begin(),x.end()
#define halt(...) {fo << (__VA_ARGS__) << '\n';exit(0);}
#define db(n) cerr << #n << " = " << n << '\n'

struct p
{
	ld x,y;
};

ld ddd(p x, p y, p z)
{
	return x.x*y.y+y.x*z.y+z.x*x.y-x.y*y.x-y.y*z.x-z.y*x.x;
}


int n;
vector<p> v;

int main()
{
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	ios_base::sync_with_stdio(0); cin.tie(0);
		
	cin>>n;
	v.resize(n);
	for (int i=0; i<n; i++)	
		cin>>v[i].x>>v[i].y;
		
	sort( all(v), [](p x, p y){ if (x.x!=y.x) return x.x<y.x; return x.y<y.y;});
	
	sort( v.begin()+1, v.end(), [=](p x, p y){ return ddd(v[0],x,y)>0;});
	
	int m  = 1;
	vector<p> h = {v[0],v[0]};
	for (int i=1; i<n; i++)
	{
		while (i<n && ddd(h[m-1],h[m],v[i])<0)
			if (m>1) h.pop_back(),m--;
			else i++;
		if (i<n) h.push_back(v[i]),m++;		
	}
	
	h.erase(h.begin());
	cout<<h.size()<<'\n';
	cout<<fixed<<setprecision(9);
	for (auto i:h)
		cout<<i.x<<' '<<i.y<<'\n';
	
	return 0;
}