Cod sursa(job #2173454)

Utilizator savigunFeleaga Dragos-George savigun Data 15 martie 2018 22:20:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct Point {
    double x, y;
};

int n, stk[120005], u;
Point p[120005];
double eps = -1e12;
vector<int> cover;


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 cmp(Point A, Point B) {
    if (A.x == B.x) {
        return A.y < B.y;
    }
    return A.x < B.x;
}

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

    sort(p + 1, p + n + 1, cmp);

    // bottom cover
    stk[++u] = 1;
    stk[++u] = 2;
    for (int i = 3; i < n; ++i) {
        while (u >= 2 && det(p[stk[u-1]], p[stk[u]], p[i]) < 0) {
            u--;
        }
        stk[++u] = i;
    }

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

    // top cover
    u = 0;
    stk[++u] = n;
    stk[++u] = n - 1;
    for (int i = n - 3; i >= 2; --i) {
        while (u >= 2 && det(p[stk[u-1]], p[stk[u]], p[i]) < 0) {
            u--;
        }
        stk[++u] = i;
    }

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

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

    for (int i : cover) {
        out << setprecision(6) << p[i].x << " " << p[i].y << "\n";
    }

    return 0;
}