Cod sursa(job #1515673)

Utilizator tain1234andrei laur tain1234 Data 2 noiembrie 2015 00:13:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stack>
#include <fstream>
#include <bitset>
#include <iomanip>
#include <algorithm>
using namespace std;
pair<double, double> PTS[120001];
double cross(const int&a, const int&b, const int&c){
	return (PTS[a].first - PTS[c].first)*(PTS[b].second - PTS[c].second) - (PTS[b].first - PTS[c].first)*(PTS[a].second - PTS[c].second);
}
const int 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(s[len], s[len - 1], i) < E)
			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";
}