Cod sursa(job #1576842)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 22 ianuarie 2016 21:45:28
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 120100

using namespace std;

struct pct
{
    double x, y;
    pct(double x = 0, double y = 0) : x(x), y(y) { }
    bool operator()(pct e, pct f)
    {
        if (e.x != f.x)
			return e.x < f.x;
		return e.y < f.x;
    }
};
pct a[MAXN];
int n;

void citire()
{
	double x, y;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lf %lf\n", &x, &y);
		a[i] = pct(x, y);
	}
	sort(a+1, a+1+n, pct());
}
vector<pct> st;

double det(pct e, pct f, pct g)
{
    return e.x * f.y + f.x * g.y + g.x * e.y -
		  (g.x * f.y + f.x * e.y + e.x * g.y);
}

void update (pct p)
{
	int last = st.size()-1;
	while (true)
		if (last == 0 || det(st[last-1], st[last], p) >= 0) {
			if (det(st[last-1], st[last], p) != 0)
				st.push_back(p);
			break;
		}
		else
			st.pop_back(), last--;
}

void solve()
{
	st.push_back(a[1]);
	st.push_back(a[2]);
	for (int i = 3; i <= n; i++) {
        update(a[i]);
	}
	for (int i = n-1; i >= 1; i--) {
		update(a[i]);
	}
	st.pop_back();
	printf("%d\n", st.size());
	for (int i = 0, t = st.size(); i <t; i++)
		printf("%lf %lf\n", st[i].x, st[i].y);
}

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

	citire();
	solve();

    return 0;
}