Cod sursa(job #811392)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 12 noiembrie 2012 05:00:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

inline double next_double() {
	double f;
	scanf("%lf", &f);
	return f;
}

struct point {
	double x, y;
	point(double x = 0, double y = 0) :
		x(x), y(y) {
	}
	bool operator<(const point & p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
};

vector<point> poly;

vector<point> upper;
vector<point> lower;
vector<point> convx;

bool convex(const point & a, const point & b, const point & c) {
	point p1(b.x - a.x, b.y - a.y);
	point p2(c.x - a.x, c.y - a.y);
	return (p1.x * p2.y - p1.y * p2.x) < 0;
}

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	int n = next_int();

	for (int i = 0; i < n; i++) {
		double x = next_double();
		double y = next_double();
		poly.push_back(point(x, y));
	}

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

	for (int i = 0; i < n; i++) {
		upper.push_back(poly[i]);
		while (upper.size() > 2 && !convex(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1])) {
			upper.erase(upper.begin() + upper.size() - 2);
		}
	}

	for (int i = n - 1; i >= 0; i--) {
		lower.push_back(poly[i]);
		while (lower.size() > 2 && !convex(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1])) {
			lower.erase(lower.begin() + lower.size() - 2);
		}
	}

	for (int i = 0; i < int(upper.size()); i++) {
		convx.push_back(upper[i]);
	}

	for (int i = 1; i < int(lower.size()) - 1; i++) {
		convx.push_back(lower[i]);
	}

	reverse(convx.begin(), convx.end());

	printf("%d\n", int(convx.size()));
	for (size_t i = 0; i < convx.size(); i++) {
		printf("%lf %lf\n", convx[i].x, convx[i].y);
	}
	return 0;
}