Cod sursa(job #1815202)

Utilizator o_micBianca Costin o_mic Data 24 noiembrie 2016 22:18:08
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <stack>
#define DN 1005
#define LD long double
#define LL long long
#define x first
#define y second
#define EPS 1e-9
using namespace std;

typedef pair<double, double> point;

point p[DN];

bool cmp(point a, point b) {
	return atan2(a.y - p[0].y, a.x - p[0].x) > atan2(b.y - p[0].y, b.x - p[0].x);
}

bool is_trigonometric(point a, point c, point b) {
	return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) > 0;
}

int main() {
	int n;
	stack<point> hull;
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");
	// freopen("input.txt", "r", stdin);
	fin >> n;
	for (int i = 0; i < n; ++i) {
		fin >> p[i].x >> p[i].y;
	}

	for (int i = 1; i < n; ++i) {
		if (p[i].x < p[0].x || (p[i].x == p[0].x && p[i].y < p[0].y))
			swap(p[0], p[i]);
	}

	sort(p+1, p+n, cmp);

	hull.push(p[0]);
	hull.push(p[1]);
	for (int i = 2; i < n; ++i) {
		point pivot = hull.top();
		hull.pop();
		point prev = hull.top();
		while (!is_trigonometric(prev, pivot, p[i])) {
			pivot = prev;
			hull.pop();
			prev = hull.top();
		}
		hull.push(pivot);
		hull.push(p[i]);
	}

	fout << hull.size() << '\n';
	while (!hull.empty()) {
		fout << hull.top().x << " " << hull.top().y << '\n';
		hull.pop();
	}
	return 0;
}