Cod sursa(job #2857863)

Utilizator ptudortudor P ptudor Data 26 februarie 2022 15:11:34
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>
#define double long double
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#endif

struct Point {
    double x,y;

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

    Point operator - (const Point other) const {
        return Point{x - other.x , y - other.y};
    }
};

double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

bool rightTurn(Point a, Point b, Point c) {
    return dot(b , a) > dot(c , b);
}
vector<Point> pt;
int n,i;
double x,y;
vector<Point> res;
Point lowLeft;

vector<Point> convexHull() {

    lowLeft = pt[1];
    for (i = 2; i <= n; i++) {
        if (pt[i] < lowLeft) {
            lowLeft = pt[i];
        }
    }
    sort(pt.begin() + 1, pt.end() , [&](Point a, Point b) {
        ///we move everyone down by this low left guy, then sort this increasing by it's angle.
        ///this is also cool cause this makes the origin(lowLeft the first one)
        return dot(a , lowLeft) < dot(b , lowLeft);
    });

    for (i = 1; i <= n; i++) {
        while(res.size() >= 2 && rightTurn(res[(int)res.size() - 2] , res[(int)res.size() - 1] , pt[i])) {
            res.pop_back();
        }
        res.push_back(pt[i]);
    }
    return res;
}

int main() {
    int N;
    in >> N;
    n = N;
    pt.resize(n + 1);
    for (i = 1; i <= n; i++) {
        int X,Y;
        in >> X >> Y;
        x = X;
        y = Y;
        pt[i] = {x,y};
    }


    convexHull();

    out << fixed << setprecision(12);
    out << res.size() << "\n";
    for (auto k : res) {
        out << k.x << " " << k.y << "\n";
    }
    out << "\n";
}