Cod sursa(job #1516038)

Utilizator tain1234andrei laur tain1234 Data 2 noiembrie 2015 17:07:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <bitset>
#include <iomanip>
#include <algorithm>
using namespace std;
pair<double, double> PTS[120001];
double cross_product(const pair<double, double>& O, const pair<double, double>& A, const pair<double, double>&  B) {
	return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - O.second);
}
const double E = 1e-12;
int s[120001], len=0;
int main(){
	ifstream f("infasuratoare.in");
	ofstream of("infasuratoare.out");
	int N;
	bitset<120001> v;
	f >> N;
	for (int i = 1; i <= N; ++i){
		f >> PTS[i].first >> PTS[i].second;
	}
	sort(PTS+1, PTS + N + 1);
	s[++len] = 1;
	s[++len] = 2;
	v[2] = 1;
	for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p)))
	if (!v[i]){
		while (len >= 2 && cross_product(PTS[s[len-1]], PTS[s[len]], PTS[i]) > 0)
			v[s[len--]] = 0;
		s[++len] = i;
		v[i] = 1;
	}
	of << len-1 <<"\n";
	of << setprecision(6) << fixed;
	for (int i = 1; i < len; ++i)
		of << PTS[s[i]].first << " " << PTS[s[i]].second << "\n";
}