Cod sursa(job #800887)

Utilizator Sm3USmeu Rares Sm3U Data 22 octombrie 2012 20:56:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <cstdio>
#include <algorithm>
#include <stack>

#define abs(x) ((x < 0) ? -x : x)
#define nMax 120005
#define inf 1009999999
#define max(a, b) ((a > b) ? a : b)

using namespace std;

struct punct{
    double x;
    double y;
    double panta;
};

int n;
punct p[nMax];
double d[nMax];
stack <punct> s;

struct cmp{
    bool operator () (const punct &a, const punct &b)const{
        return a.panta > b.panta;
    }
};


double panta (punct p1, punct p2){
    if (p1.x - p2.x == 0){
        return inf;
    }
    return (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
}

double determinant (punct p1, punct p2, punct p3){
    return p1.x * p2.y  + p2.x * p3.y + p1.y * p3.x
        - p3.x * p2.y - p1.y * p2.x - p1.x * p3.y;
}

void citire(){
    punct pMin;
    pMin.x = inf;
    pMin.y = inf;
    scanf ("%d", &n);
    int pct;
    for (int i = 0; i < n; ++ i){
        scanf ("%lf %lf", &p[i].x, &p[i].y);
        if (p[i].x < pMin.x){
            pMin = p[i];
            pct = i;
        }else if (p[i].x == pMin.x){
            if (p[i].y < pMin.y){
                pMin = p[i];
                pct = i;
            }
        }
    }
    for (int i = 0; i < n; ++ i){
        p[i].panta = panta (pMin, p[i]);
    }
    p[pct].panta = inf + 1;
    sort (p, p + n, cmp());
}


void infasoara(){
    s.push (p[0]);
    s.push (p[1]);
    int nr = 2;
    for (int i = 2; i < n; ++ i){
        punct p2 = s.top();
        s.pop();
        nr --;
        punct p1 = s.top();
        while (determinant(p1, p2, p[i]) > 0){
            p2 = p1;
            s.pop();
            p1 = s.top();
            nr --;
        }
        s.push (p2);
        s.push (p[i]);
        nr += 2;
    }
    printf ("%d\n", nr);
    while (!s.empty()){
        printf ("%lf %lf\n", s.top().x, s.top().y);
        s.pop();
    }
}

int main(){

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

    citire();
    infasoara();

    return 0;
}