Cod sursa(job #1109703)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 17 februarie 2014 15:04:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <algorithm>

#define x first
#define y second
#define NMAX 120007

using namespace std;

pair<double, double> a[NMAX], Stack[NMAX];
int n;

inline double cp( pair<double , double> A , pair<double , double> B , pair<double , double> C){
    return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}

inline int cmp(pair<double, double> p1,pair<double, double> p2){
    return cp(a[1] , p1 , p2) < 0;
}

int infasuratoare(){
    int poz = 1;
    for (int i = 2; i <= n; ++i)
        if(a[i] < a[poz])
            poz = i;
    swap(a[1], a[poz]);
    sort(a + 2, a + n + 1, cmp);
    Stack[1] = a[1];
    Stack[2] = a[2];
    int nr = 2;
    for(int i = 3; i <= n; ++i){
        while(nr >= 3 && cp(Stack[nr - 1], Stack[nr], a[i]) > 0)
            --nr;
        Stack[++nr] = a[i];
    }
    return nr;
}

int main(){
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d\n", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf %lf", &a[i].x, &a[i].y);
    n = infasuratoare();
    printf("%d\n", n);
    for(int i = n; i >= 1; --i)
        printf("%.6lf %.6lf\n", Stack[i].x, Stack[i].y);
    return 0;
}