Cod sursa(job #1815745)

Utilizator o_micBianca Costin o_mic Data 25 noiembrie 2016 18:35:21
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#define DN 120005
#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];
map<point, double> angle;

bool cmp(point a, point b) {
	return angle[a] > angle[b];
}

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;
}

point hull[DN];
int m;

int main() {
	int n;
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");
	// freopen("input.txt", "r", stdin);
	// ifstream fin("input.txt");
	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]);
	}

	for (int i = 1; i < n; ++i)
		angle[p[i]] = atan2(p[i].y - p[0].y, p[i].x - p[0].x);
	
	sort(p+1, p+n, cmp);

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

	fout << m << '\n';
	while (m) {
		--m;
		fout << fixed << setprecision(12) << hull[m].x << " " << hull[m].y << '\n';
	}
	return 0;
}