Cod sursa(job #2526346)

Utilizator razviii237Uzum Razvan razviii237 Data 18 ianuarie 2020 15:19:37
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int maxn = 120005;

struct xy {
    double x, y;
    bool operator < (xy other) {
        if((*this).x == other.x) {
            return (*this).y < other.y;
        }
        return (*this).x < other.x;
    }
    bool operator > (xy other) {
        if((*this).x == other.x) {
            return (*this).y > other.y;
        }
        return (*this).x > other.x;
    }
};

xy v[maxn], mn;
xy st[maxn]; int k;
int n, i;

double determinant(xy a, xy b, xy c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(xy a, xy b) {
    return determinant(v[1], a, b) < 0;
}

void sortpoints() {
    int pos = 1;
    mn = v[1];
    for(i = 2; i <= n; i ++) {
        if(v[i] < mn) {
            mn = v[i]; pos = i;
        }
    }
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, cmp);
}

void convexhull() {
    st[1] = v[1];
    st[2] = v[2];
    k = 2;
    for(i = 3; i <= n; i ++) {
        while(k > 2 && determinant(st[k-1], st[k], v[i]) > 0) {
            -- k;
        }
        st[++k] = v[i];
    }
}

int main()
{
    g << fixed << setprecision(9);
    f >> n;
    for(i = 1; i <= n; i ++) {
        f >> v[i].x >> v[i].y;
    }

    sortpoints();
    convexhull();

    g << k << '\n';
    for(i = k; i >= 1; i --) {
        g << st[i].x << ' ' << st[i].y << '\n';
    }

    f.close(); g.close();
    return 0;
}