Cod sursa(job #1721075)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 iunie 2016 13:02:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;

struct punct{
	double x, y; };

double cross_product(const punct& p1, const punct& p2){
	return p1.x * p2.y - p2.x * p1.y; }

bool is_left_turn(const punct& p1, const punct& p2, const punct& p3){
	return cross_product(punct{ p1.x - p2.x, p1.y - p2.y},
			punct{ p3.x - p2.x, p3.y - p2.y }) < 0; }

auto x_cmp = [](const punct& p1, const punct& p2){
	return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); };

template <typename T>
T& sec_back(vector<T>& v){
	return v[v.size()-2]; }

vector<punct> mk_half_infasuratoare(const vector<punct>& pts){
	vector<punct> rez = {pts[0]};
	for(int i = 1; i < pts.size(); ++i){
		const auto p = pts[i];
		while(rez.size() > 1 && !is_left_turn(sec_back(rez), rez.back(), p)){
			rez.pop_back(); }
		rez.push_back(p); }
	return rez; }

vector<punct> mk_infasuratoare(vector<punct>& pts){
	sort(begin(pts), end(pts), x_cmp);
	vector<punct> under, over;

	under.push_back(pts[0]);
	over.push_back(pts[0]);
	for(int i = 1; i < pts.size()-1; ++i){
		const auto p = pts[i];
		(is_left_turn(pts[0], pts.back(), p) ? over : under).push_back(p); }
	under.push_back(pts.back());
	over.push_back(pts.back());

	reverse(begin(over), end(over));

	auto inf_over = mk_half_infasuratoare(over),
		  inf_under = mk_half_infasuratoare(under);
	inf_under.pop_back(), inf_over.pop_back();

	inf_under.insert(end(inf_under), begin(inf_over), end(inf_over));

	return inf_under; }

int main(){
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	int n;
	f >> n;

	vector<punct> pts(n);
	for(auto& p : pts){
		f >> p.x >> p.y; }

	vector<punct> rez = mk_infasuratoare(pts);

	g << rez.size() << '\n';
	g << fixed << setprecision(6);
	for(const auto p : rez){
		g << p.x << ' ' << p.y << '\n'; }

	return 0; }