Cod sursa(job #1546257)

Utilizator toniobFMI - Barbalau Antonio toniob Data 7 decembrie 2015 21:04:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
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(double d) {
	return d < 0;
}
bool vs(double d) {
	return d > 0;
}

void scan(bool (*vc)(double), 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()-2], l[l.size() - 1], v[i] )) ) {
			l.erase(l.begin() + l.size() - 1);
		}
		l.push_back(v[i]);

	}
}

bool comp(punct a, punct b) {
	return vs( det( v[0], a, b ) );
}

int main() {

	in >> n;
	int pozMin = 0;
	for (int i = 0; i < n; ++i) {
		in >> v[i].x >> v[i].y;
		if ((v[i].x == v[pozMin].x && v[i].y < v[pozMin].y) || v[i].x < v[pozMin].x) {
			pozMin = i;
		}
	}
	punct aux = v[0];
	v[0] = v[pozMin];
	v[pozMin] = aux;
	sort(v + 1, v + n, comp);
	//for (int i = 0; i < n; ++i) {
	//	cout << v[i].x << ' ' << v[i].y << '\n';
	//}
	//cout << "\n\n";

	scan(vs, l1);

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

	return 0;
}