Cod sursa(job #2108501)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 18 ianuarie 2018 14:21:20
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define X first
#define Y second
#define eps 1e-12

using namespace std;

typedef pair<double, double> point;
vector<point> points;
vector<point> sol;

void read() {

	ifstream in("infasuratoare.in");

	int n;
	double x, y;
	int left = 0;

	for (in >> n; n; --n) {

		in >> x >> y;
		points.push_back(make_pair(x, y));
		
		if (x - points.back().X <= -eps || (fabs(x - points.back().X) < eps && y - points.back().Y <= -eps))
			left = points.size() - 1;
	}

	swap(points[0], points[left]);

	in.close();
}

double crossProduct(const point& p, const point& q, const point& r) {

	return (q.X - p.X) * (r.Y - p.Y) - (r.X - p.X) * (q.Y - p.Y);
}

double dist(const point& p, const point& q) {

	return (q.X - p.X) * (q.X - p.X) + (q.Y - p.Y) * (q.Y - p.Y);
}

bool compare(const point& p1, const point &p2) {

	double orientation = crossProduct(points[0], p1, p2);
	
	if (orientation >= eps || (fabs(orientation) < eps && dist(points[0], p1) < dist(points[0], p2)))
		return true;

	return false;
}

int main() {

	read();

	sort(points.begin() + 1, points.end(), compare);

	for (const point &p : points) {

		while (sol.size() >= 2 && crossProduct(sol[sol.size() - 2], sol.back(), p) < eps)
			sol.pop_back();

		sol.push_back(p);
	}

	ofstream out("infasuratoare.out");
	out << sol.size() << "\n";
	out << fixed << setprecision(6);

	for (const point &p : sol)
		out << p.X << " " << p.Y << "\n";
	out.close();
	return 0;
}