Cod sursa(job #2858470)

Utilizator ptudortudor P ptudor Data 27 februarie 2022 16:58:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>
#define ld 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 {
    ld x,y;
    Point operator - (const Point other) const {
        return {x - other.x , y - other.y};
    }
    bool operator < (const Point other) const {
        ///we want the left-most point, and the lowest one if possible
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
};
bool rightTurn(Point a, Point b, Point c) {
    return b.x * c.y + c.x * a.y + a.x * b.y - b.x * a.y - c.x * b.y - a.x * c.y < 0;
}
vector<Point> pt;
int n;

vector<Point> res;
void convexHull() {
    int leftLow = 1;
    for (int i = 2; i <= n; i++) {
        if (pt[i] < pt[leftLow]) {
            leftLow = i;
        }
    }
    swap(pt[1] , pt[leftLow]); // leftLow is the first one;
    sort(pt.begin() + 2, pt.end() , [&](Point p1, Point p2) {
        /// y / x < y2 / x2
        Point o_p1 = p1 - pt[1];
        Point o_p2 = p2 - pt[1];
        return o_p1.y * o_p2.x < o_p2.y * o_p1.x;
    });

    for (int i = 1; i <= n; i++) {
        int rs = (int)res.size();
        while(rs >= 2 && rightTurn(res[rs - 2] , res[rs - 1] , pt[i])) {
            res.pop_back();
            rs = (int)res.size();
        }
        res.push_back(pt[i]);
    }
}
int main() {
    in >> n;
    pt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        ld x,y;
        in >> pt[i].x >> pt[i].y;
    }

    convexHull();

    out << fixed << setprecision(12);
    out << res.size() << "\n";

    int topPoint = 0;
    for (int i = 1; i < res.size(); i++) {
        if (res[i].y < res[topPoint].y) {
            topPoint = i;
        } else if (res[i].y == res[topPoint].y && res[i].x < res[topPoint].x) {
            topPoint = i;
        }
    }
    for (int i = topPoint;i < res.size(); i++) {
        out << res[i].x << " " << res[i].y << "\n";
    }

    for (int i = 0;i < topPoint; i++) {
        out << res[i].x << " " << res[i].y << "\n";
    }
}