Cod sursa(job #915315)

Utilizator Sm3USmeu Rares Sm3U Data 14 martie 2013 21:51:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cstdio>
#include <algorithm>

#define nMax 120100
#define oo 1 << 30

using namespace std;

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

punct a[nMax];
int p[nMax];
int n;
int minim = oo;
int pmin;
int m;

double panta(punct a, punct b){
    if(a.x - b.x == 0){
        return oo;
    }
    return (double)(a.y - b.y)/(double)(a.x - b.x);
}

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

/**
a.x | a.y | 1
b.x | b.y | 1
c.x | c.y | 1
*/
double determinant(punct a, punct b, punct c){
    return a.x * b.y + a.y * c.x + b.x * c.y
        -b.y * c.x - c.y * a.x - a.y * b.x;
}

void citire(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        scanf("%lf %lf", &a[i].x, &a[i].y);
        if(a[i].x <= minim){
            if(a[i].x == minim){
                if(a[i].y < a[pmin].y){
                    pmin = i;
                }
            }else{
                pmin = i;
                minim = a[i].x;
            }
        }
    }
    for(int i = 0; i < n; ++ i){
        a[i].panta = panta(a[pmin], a[i]);
    }
    a[pmin].panta = -oo - 1;
    sort(a, a + n, cmp());
}

void infasuratoare(){
    m = 2;
    p[0] = 0;
    p[1] = 1;
    for(int i = 2; i < n; ++ i){
        while(m > 2 && determinant(a[p[m - 2]], a[p[m - 1]], a[i]) < 0){
            m --;
        }
        p[m ++] = i;
    }
}

void afisare(){
    printf("%d\n", m);
    for(int i = 0; i < m; ++ i){
        printf("%lf %lf\n", a[p[i]].x, a[p[i]].y);
    }
}

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

    citire();
    infasuratoare();
    afisare();

    return 0;
}