Cod sursa(job #881431)

Utilizator raluca_vacaruVacaru Raluca-Ioana raluca_vacaru Data 17 februarie 2013 22:48:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 120001

using namespace std;

struct point {
    double x, y;
};

int n, nr;
int ch[MAXN];
point p[MAXN];

void read () {
    int i;
    ifstream f ("in.txt");
    f>>n;
    for (i=1; i<=n; ++i)
        f>>p[i].x>>p[i].y;
    f.close();
}

bool comp (point a, point b) {
    if (a.y < b.y) return true;
    if (a.y > b.y) return false;
    if (a.x < b.x) return true;
    return false;
}

bool valid (point a, point b, point c) {
    //true daca c e la dreapta dreptei ab
    double d;
    d = a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
    if (d < 0) return true;
    return false;
}

void convex_hull () {
    ch[++nr] = 1; ch[++nr] = 2;
    bool ok=0;
    int i=3, k;
    //pana sus
    while (!ok) {
        if (i==n) ok = !ok;
        if (!valid(p[ch[nr-1]], p[ch[nr]], p[i])) ch[++nr] = i;
        else {
            k=0;
            do { ch[nr-k] = i; ++k;
            } while (valid(p[ch[nr-2]], p[ch[nr-1]], p[ch[nr]]));
            nr -= k-1;
        }
        ++i;
    }
    //inapoi jos
    i-=2;
    ch[++nr] = i--;
    while (ok) {
        if (i==1) ok = !ok;
        if (valid(p[ch[nr]], p[ch[nr-1]], p[i])) ch[++nr] = i;
        else {
            k=0;
            do { ch[nr-k] = i; ++k;
            } while (valid(p[ch[nr-2]], p[ch[nr-1]], p[ch[nr]]));
            nr -= k-1;
        }
        --i;
    }
    --nr;
}

void write () {
    //freopen ("out.txt", "w", stdout);
    int i;
    cout<<nr<<'\n';
    for (i=1; i<=nr; ++i)
        cout<<p[ch[i]].x<<' '<<p[ch[i]].y<<'\n';
    //fclose(stdin);
}

int main () {
    read ();
    sort (p, p+n+1, comp);
    convex_hull ();
    write ();
    return 0;
}