Cod sursa(job #1822848)

Utilizator mucalmicmarcel almic mucalmic Data 5 decembrie 2016 18:01:59
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>


using namespace std; 

struct Point{
	double x, y;
	Point(pair<double, double> pa): x(pa.first), y(pa.second) {}
};

double prod (Point a, Point b, Point c) {
	return (c.y - a.y)*(b.x - a.x) - (c.x - a.x)*(b.y - a.y);
}

int main() {
	const double eps = 1e-12;
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");
	int n;
	fin>>n;
	vector <pair <double, double>> v(n);
	vector <int> sol(n), vis(n, 0);
	for (auto &p: v) {
		fin>>p.first>>p.second;
	}
	
	//vis[0] = 1;  we want to meet this point again, so we don't mark visited
	sort(v.begin(), v.end());
	
	sol[0] = 0;
	sol[1] = 1;
	int m = 2;
	vis[0] = vis[1] = 1;
	for (int i = 2; i < n; i++) {
		Point nou = Point(v[i]);
		while (m > 1 && prod(Point(v[sol[m-2]]), Point(v[sol[m-1]]), nou) < eps)
			vis[sol[--m]] = 0;
		sol[m] = i;
		vis[sol[m++]] = 1;
	}
	
	for (int i = n-1; i > 0; i--) {
		Point nou = Point(v[i]);
		if (vis[i])
			continue;
		while (m > 1 && prod(Point(v[sol[m-2]]), Point(v[sol[m-1]]), nou) < eps)
			m--;
		sol[m++] = i;
	}
	
	fout<<m<<endl;
	fout << setprecision(6) << fixed;
	for (int i = 0; i < m; i++)
		fout<<v[sol[i]].first<<" "<<v[sol[i]].second<<endl;
		
	return 0;
	

}