Cod sursa(job #719772)

Utilizator deneoAdrian Craciun deneo Data 22 martie 2012 01:15:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define lung 200000

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point {
    double x, y;
};

int stiva[lung], ps = 1, n, v[lung];
point p[lung];

bool cmp(int i, int j) {
    return (p[i].x - p[ps].x) * (p[j].y - p[ps].y) > (p[j].x - p[ps].x) * (p[i].y - p[ps].y);
}

long double semn(int i1, int i2, int i3)
{
	return (long double)p[i1].x * p[i2].y + p[i2].x * p[i3].y + p[i3].x * p[i1].y - p[i1].y * p[i2].x - p[i2].y * p[i3].x - p[i3].y * p[i1].x;
}

int main() {
    int i;
    fin >> n;
    for (i = 1; i <= n; ++i) {
        fin >> p[i].x >> p[i].y;
        if (p[i].x < p[ps].x || (p[i].x == p[ps].x && p[i].y < p[ps].y))
            ps = i;
    }
    for (i = 1; i <= n; ++i) {
        if (i == ps) continue;
        v[++v[0]] = i;
    }

    sort(v + 1, v + v[0] + 1, cmp);
    for (i = 1; i < n; ++i) {
        if (stiva[0] >= 2 && (semn(stiva[stiva[0] - 1], v[i], stiva[stiva[0]]) > 0)) --stiva[0];
        stiva[++stiva[0]] = v[i];
    }
    stiva[++stiva[0]] = ps;
    fout << stiva[0] << "\n";
    for(i = 1; i <= stiva[0]; ++i)
        fout << p[stiva[i]].x << " " << p[stiva[i]].y << "\n";
    fout.close();
    return 0;
}