Cod sursa(job #2227566)

Utilizator andreioneaAndrei Onea andreionea Data 1 august 2018 03:23:07
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

struct Point{
	double x = 0;
	double y = 0;
};

double ccw(const Point& p1, const Point& p2, const Point& p3)
{
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}


inline std::istream& operator >>(std::istream& in, Point& p)
{
	in >> p.x >> p.y;
	return in;
}



int main()
{
	std::ifstream fin("infasuratoare.in");
	std::ofstream fout("infasuratoare.out");
	int N;
	std::vector<Point> points;
	fin >> N;
	Point best;
	bool first = true;
	for (int i = 0; i < N; ++i) {
		Point p;
		fin >> p;
		if (first||(p.x <= best.x && p.y <= best.y)) {
			if(!first) {
				points.push_back(best);
			}
			best = p;
		} else {
			points.push_back(p);
		}
		first = false;
	}
	const auto cmp = [&best](const Point& lhs, const Point& rhs)->bool {return ccw(best, lhs, rhs) > 0;};
	std::sort(points.begin(), points.end(),cmp);
	std::vector<Point> hull;
	hull.push_back(best);
	for(const auto& p : points) {
		if (hull.size() < 3) {
			hull.push_back(p);
		} else {
			bool positiveDotProd = false;
			do {
				const auto& P2 = hull.back();
				const auto& P1 = *(hull.rbegin() + 1);
				positiveDotProd = ccw(P1, P2, p) > 1e-12;
				if (!positiveDotProd) {
					hull.pop_back();
				}

			} while(!positiveDotProd && hull.size() > 2);
			hull.push_back(p);
		}
	}
	fout << hull.size() << "\n";
	fout << std::setprecision(6) << std::fixed;
	for (const auto& p : hull) {
		fout << p.x << " " << p.y << "\n";
	}
	return 0;
}