Cod sursa(job #1731854)

Utilizator mikeshadowIon Complot mikeshadow Data 20 iulie 2016 07:10:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long double LD;
typedef pair<LD, LD> PLD;
PLD v[400000], h[400000];
int n,j;
bool d(PLD a, PLD b, PLD c)
{
	return (a.x-c.x)*(b.y-c.y) - (a.y-c.y)*(b.x-c.x) < 0;
}

int main(){
	freopen("infasuratoare.in", "rt", stdin);
	freopen("infasuratoare.out", "wt", stdout);
	cin>>n;
	for(int i=0; i<n; ++i)
		cin>>v[i].x>>v[i].y;
	sort(v, v+n);
	reverse_copy(v, v+n-1, v+n);
	for(int i=0; i<2*n-1; h[j++]=v[i++])
		while(j>1 && d(h[j-2], h[j-1], v[i]))
			j--;
	j--;
	cout<<j<<"\n";
	cout<<setprecision(9)<<fixed;
	for(int i=0; i<j; ++i)
		cout<<h[i].x<<" "<<h[i].y<<"\n"; 
	return 0;
}