Cod sursa(job #2570204)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 4 martie 2020 15:34:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <iomanip>

using namespace std;

struct Point {
    long double x, y;

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

long double det3(const Point &a, const Point &b, const Point &c) {
    /// a.x a.y 1
    /// b.x b.y 1
    /// c.x c.y 1
    return (a.x * b.y + b.x * c.y + a.y * c.x - c.x * b.y - c.y * a.x - b.x * a.y);
}

Point aux;
bool cmp(const Point &a, const Point &b) {
    long double x = det3(aux, a, b);
    if(x == 0)
        return a < b;
    else
        return x > 0;
}

int main() {
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    int n;
    in >> n;
    vector<Point> v(n + 1);
    for(int i = 1; i <= n; i ++)
        in >> v[i].x >> v[i].y;
    int start = 1;
    for(int i = 2; i <= n; i ++)
        if(v[i] < v[start])
            start = i;
    swap(v[1], v[start]);
    aux = v[1];
    sort(v.begin() + 2, v.end(), cmp);

    vector<int> stk(n + 1, 0);
    int sz = 0;
    for(int i = 1; i <= n; i ++) {
        while(sz > 1 && det3(v[stk[sz - 1]], v[stk[sz]], v[i]) < 0)
            sz --;
        stk[++ sz] = i;
    }

    out << sz << "\n";
    for(int i = 1; i <= sz; i ++)
        out << setprecision(10) << fixed << v[stk[i]].x << " " << v[stk[i]].y << "\n";

    return 0;
}