Cod sursa(job #1721071)

Utilizator wilson182Alexandrina Panfil wilson182 Data 24 iunie 2016 12:33:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<bits/stdc++.h>
#define x first
#define y second
#define N 240050
#define p pair<double, double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
p v[N], h[N];
int m, j;
bool s(p a, p b, p c)
{
	return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x) < 0;
}
int main ()
{
	f >> m;
	for (int i = 0; i < m; i++) f>>v[i].x>>v[i].y;
	sort(v, v + m); reverse_copy(v, v + m - 1, v + m);
	for (int i = 0; i < m*2 - 1; h[j++] = v[i++])
	while (j > 1 && s(h[j-2], h[j-1], v[i])) --j;
	g<<--j;
	for (int i=0; i<j; ++i) g<<fixed<<setprecision(9)<<'\n'<<h[i].x<<" "<<h[i].y;
	return 0;
}