Cod sursa(job #3353776)

Utilizator petru-robuRobu Petru petru-robu Data 11 mai 2026 13:28:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <bits/stdc++.h>
using namespace std;

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

class Point{
public:
    double x, y;

    Point(double x, double y): x(x), y(y) {}

    friend istream& operator>>(istream& is, Point& p) {
        is >> p.x >> p.y;
        return is;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        os << fixed << setprecision(6) << p.x << ' ' << p.y;
        return os;
    }

    bool operator==(const Point& p1) const {
        return p1.x == x && p1.y == y;
    }
};

int n;
vector<Point> points;

double dist2(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
}

/*
    delta > 0 => left
    delta < 0 => right 
    delta = 0 => colinear
*/
double delta(Point A, Point B, Point C) {
    double xa = A.x, ya = A.y;
    double xb = B.x, yb = B.y;
    double xc = C.x, yc = C.y;
    return xa * (yb - yc) + xb * (yc - ya) + xc * (ya - yb);
    
}

void read() {
    fin >> n;
    for(int i = 0; i < n; i++) {
        double x, y;
        fin >> x >> y;
        points.push_back(Point(x, y));
    }
}   


vector<Point> graham_scan() {
    // start point
    int idx = 0;
    for(int i = 1; i < n; i++) {
        if(points[i].y < points[idx].y || (points[i].y == points[idx].y && points[i].x < points[idx].x))
            idx = i;
    }

    swap(points[0], points[idx]);
    Point start = points[0];

    // sortare dupa unghi
    sort(points.begin() + 1, points.end(),
        [&](const Point& a, const Point& b) {
            double cross = delta(start, a, b);

            // start, a, b sunt cooliniare
            if(cross == 0) 
                return dist2(start, a) < dist2(start, b);

            return cross > 0;
        }
    );

    // scan
    stack<Point> s;
    s.push(points[0]);
    s.push(points[1]);

    for(int i = 2; i < n; i++) {
        while(s.size() >= 2) {
            Point top = s.top();
            s.pop();
            Point next = s.top();

            // left turn
            if(delta(next, top, points[i]) > 0) {
                s.push(top);
                break;
            }
        }

        s.push(points[i]);
    }

    // get the hull
    vector<Point> hull;

    while(!s.empty()) {
        hull.push_back(s.top());
        s.pop();
    }

    reverse(hull.begin(), hull.end());
    return hull;
}

int main() {
    read();
    auto hull = graham_scan();

    fout << hull.size() << "\n";
    for(auto &x : hull) {
        fout << x << '\n';
    }

    return 0;
}