Cod sursa(job #1983949)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 22 mai 2017 22:47:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct point {
    double x, y;

    bool operator< (const point& other) const {
        if (x != other.x)
            return x < other.x;
        return y < other.y;
    }
};

const int NMAX = 120002;

int n;
point v[NMAX];
point stk[NMAX];
int stackTop;

inline void read() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i].x >> v[i].y;
    }
}

inline double crossProduct(const point& a, const point& b, const point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool cmp(const point& a, const point& b) {
    return crossProduct(v[1], a, b) < 0;
}

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

inline void convexHull() {
    sortPoints();

    stk[1] = v[1];
    stk[2] = v[2];
    stackTop = 2;
    for (int i = 3; i <= n; ++i) {
        while (stackTop >= 2 && crossProduct(stk[stackTop - 1], stk[stackTop], v[i]) > 0)
            --stackTop;
        stk[++stackTop] = v[i];
    }
}

inline void write() {
    fout << stackTop << '\n';
    for (int i = stackTop; i; --i)
        fout << fixed << setprecision(9) << stk[i].x << ' ' << stk[i].y << '\n';
}

int main()
{
    read();
    convexHull();
    write();

    fin.close();
    fout.close();
    return 0;
}