Cod sursa(job #1398930)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 24 martie 2015 14:22:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Point {
	double x,y;
};

bool operator<(const Point &a, const Point &b) {
	if(a.x == b.x) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

double cross(Point p1, Point p2, Point p3) {
	return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p1.y*p2.x - p2.y*p3.x - p3.y*p1.x; 
}

int main() {
	ifstream in("infasuratoare.in");
	unsigned n;
	in >> n;

	vector<Point> points(n);

	for(Point &p:points) {
		in >> p.x >> p.y;
	}

	sort(points.begin(), points.end());

	vector<Point> top;

	for(unsigned i = 0; i < points.size(); ++i) {
		while(top.size() >= 2 && cross(*(top.end()-2),*(top.end()-1),points[i]) <= 0) {
			top.pop_back();
		}
		top.push_back(points[i]);
	}
	top.pop_back();

	vector<Point> bottom;
	for(int i = points.size()-1; i >= 0; --i) {
		while(bottom.size() >= 2 && cross(*(bottom.end()-2),*(bottom.end()-1),points[i]) <= 0) {
			bottom.pop_back();
		}
		bottom.push_back(points[i]);
	}
	bottom.pop_back();


	ofstream out("infasuratoare.out");
	out << top.size() + bottom.size() << '\n';
	out << setprecision(6) << fixed;
	for(Point p:top) {
		out << p.x << ' ' << p.y << '\n';
	}
	for(Point p:bottom) {
		out << p.x << ' ' << p.y << '\n';
	}

	return 0;
}