Cod sursa(job #2011909)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 17 august 2017 15:14:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>
#include <stack>

using namespace std;

const int nmax = 120000;

struct Point {
    double x, y;

    bool operator< (Point other) const {
        if(x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
} v[1 + nmax];

int st[1 + nmax];

double det3(Point a, Point b, Point c) {
    double adun, scad;
    adun = a.x * b.y + a.y * c.x + b.x * c.y;
    scad = a.x * c.y + a.y * b.x + b.y * c.x;
    return (adun - scad);
}

bool cmp(Point a, Point b) {
    return (det3(v[1], a, b) > 0);
}



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

    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        scanf("%lf%lf", &v[i].x, &v[i].y);
        if(i > 1 && v[i] < v[1]) {
            swap(v[1], v[i]);
        }
    }


    sort(v + 2, v + n + 1, cmp);

    int nsol = 2, j = 3;
    st[1] = 1, st[2] = 2;

    while(j <= n) {
        if(det3(v[st[nsol - 1]], v[st[nsol]], v[j]) > 0) {
            st[++ nsol] = j ++;
        } else {
            -- nsol;
        }
    }

    printf("%d\n", nsol);
    for(int i = 1; i <= nsol; ++ i) {
        printf("%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
    }

    return 0;
}