Cod sursa(job #1546187)

Utilizator toniobFMI - Barbalau Antonio toniob Data 7 decembrie 2015 19:55:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int nMax = 120010;
int n;
struct punct {
	double x, y;
};
punct v[nMax];
vector<punct> l1, l2;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

double det(punct p, punct q, punct r) {
	return (q.x - p.x)*(r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}
bool vd(int d) {
	return d < 0;
}
bool vs(int d) {
	return d > 0;
}

void scan(bool (*vc)(int), vector<punct> &l) {
	l.push_back(v[0]);
	l.push_back(v[1]);

	for (int i = 2; i < n; ++i) {
		
		while ( l.size() > 1 && vc(det( l[l.size()-1], l[l.size() - 2], v[i] )) ) {
			l.erase(l.begin() + l.size() - 1);
		}
		l.push_back(v[i]);

	}
}

bool comp(punct a, punct b) {
	if (a.x == b.x) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

int main() {

	in >> n;
	for (int i = 0; i < n; ++i) {
		in >> v[i].x >> v[i].y;
	}
	sort(v, v + n, comp);

	scan(vd, l1);
	scan(vs, l2);

	bool primu = false, ultimu = false;
	if (l1[l1.size() - 1].x == l2[l2.size() - 1].x && l1[l1.size() - 1].y == l2[l2.size() -1].y) {
		primu = true;
	}
	if (l1[0].x == l2[0].x && l1[0].y == l2[0].y) {
		ultimu = true;
	}

	out << l1.size() + l2.size() - primu - ultimu << '\n';
	for (vector<punct>::iterator it = l1.begin(); it != l1.end(); ++it) {
		out << it -> x << ' ' << it -> y << '\n';
	}
	for (vector<punct>::iterator it = l2.end() - 2; it != l2.begin(); --it) {
		out << it -> x << ' ' << it -> y << '\n';
	}

	return 0;
}