Cod sursa(job #1577030)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 23 ianuarie 2016 10:24:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 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.y;
    }
};
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--;
	/// Era gresit comparatorul din sortare firar sa fie....
	for (int last = st.size()-1; last && det(st[last-1], st[last], p) < 0; last--)
		st.pop_back();
	st.push_back(p);
}

void solve()
{
	st.push_back(a[1]);
	for (int i = 2; 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;
}