Cod sursa(job #3340442)

Utilizator andrei_obrejaAndrei Obreja andrei_obreja Data 14 februarie 2026 11:46:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
};
double cross(Point A, Point B, Point C) {
    return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
}
double dist(Point A, Point B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y)* (A.y - B.y));
}
bool cmp(Point a, Point b, Point p0) {
    double cr = cross(p0, a, b);
    if(fabs(cr) < 1e-12)
        return dist(a, p0) < dist(b, p0);
    return cr > 0;
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int N; fin >> N;
    vector<Point> pts(N);
    for(int i = 0; i < N; i++)
        fin >> pts[i].x >> pts[i].y;
    Point p0 = pts[0];
    for(auto &p: pts)
        if(p.y < p0.y || (p.y == p0.y && p.x < p0.x))
            p0 = p;
    sort(pts.begin(), pts.end(), [&](Point a, Point b){
        return cmp(a,b,p0);
    });
    vector<Point> hull;
    for(auto p: pts) {
        while(hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }
    fout << hull.size() << "\n";
    for(auto p: hull)
        fout << fixed << setprecision(6) << p.x << " " << p.y << "\n";

    return 0;
}