Cod sursa(job #2002851)

Utilizator savigunFeleaga Dragos-George savigun Data 20 iulie 2017 22:56:51
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

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

struct Point { double x, y; };
int n, tr[120005], u;
Point v[120005];
int st[120005];
vector<int> sol;
const double eps = 1e-12;

inline double det(Point A, Point B, Point C) {
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

bool ok() {
    Point A = v[st[u - 2]];
    Point B = v[st[u - 1]];
    Point C = v[st[u]];
    if (det(A, B, C) > 0) return true;
    return false;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; ++i) {
        in >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + n + 1, [](Point a, Point b) -> bool {
        if (a.x < b.x) return true;
        if (a.x == b.x) return a.y < b.y;
        return false;
    });

    st[++u] = 1;
    st[++u] = 2;
    for (int i = 3; i <= n; ++i) {
        st[++u] = i;

        while (!ok()) {
            st[u-1] = st[u];
            u--;
        }
    }

    for (int i = 1; i <= u; ++i) {
        sol.push_back(st[i]);
    }

    u = 0;
    st[++u] = n;
    st[++u] = n-1;

    for (int i = n - 2; i >= 1; --i) {
        st[++u] = i;

        while (!ok()) {
            st[u-1] = st[u];
            u--;
        }
    }

     for (int i = 2; i < u; ++i) {
        sol.push_back(st[i]);
    }

    out << sol.size() << "\n";

    for (int i = 0; i < sol.size(); ++i) {
        out << fixed << setprecision(6) << v[sol[i]].x << " " << v[sol[i]].y << "\n";
    }

    return 0;
}