Cod sursa(job #3233152)

Utilizator AndreiDocaDoca Andrei AndreiDoca Data 2 iunie 2024 17:28:45
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

struct Point {
    double x, y;
};

bool compare(Point a, Point b) {
    if (a.y == b.y) {
        return a.x < b.x;
    }
    return a.y < b.y;
}

double crossProduct(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

bool polarOrder(Point a, Point b, Point origin) {
    double order = crossProduct(origin, a, b);
    if (order == 0) {
        double distA = (origin.x - a.x) * (origin.x - a.x) + (origin.y - a.y) * (origin.y - a.y);
        double distB = (origin.x - b.x) * (origin.x - b.x) + (origin.y - b.y) * (origin.y - b.y);
        return distA < distB;
    }
    return order > 0;
}

vector<Point> grahamScan(vector<Point>& points) {
    vector<Point> hull;

    if (points.size() < 3) return hull;

    // Step 1: Sort points by y-coordinate (breaking ties by x-coordinate)
    sort(points.begin(), points.end(), compare);

    // Step 2: Sort points by polar angle with the first point
    Point p0 = points[0];
    sort(points.begin() + 1, points.end(), [p0](Point a, Point b) { return polarOrder(a, b, p0); });

    // Step 3: Create the convex hull
    hull.push_back(points[0]);
    hull.push_back(points[1]);

    for (size_t i = 2; i < points.size(); i++) {
        while (hull.size() > 1 && crossProduct(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    return hull;
}

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

    int N;
    fin >> N;

    vector<Point> points(N);
    for (int i = 0; i < N; ++i) {
        fin >> points[i].x >> points[i].y;
    }

    vector<Point> convexHull = grahamScan(points);

    fout << convexHull.size() << endl;
    for (const auto& point : convexHull) {
        fout << fixed << setprecision(6) << point.x << " " << point.y << endl;
    }

    return 0;
}