Cod sursa(job #3210258)

Utilizator AndreiMLCChesauan Andrei AndreiMLC Data 5 martie 2024 18:02:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

const int NMAX = 120005;

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

int N;

struct Point {
    long double x, y;
    long double angle;
};

Point points[NMAX];
int hull[NMAX];
int H;

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

bool is_counter_clockwise(Point a, Point b, Point c) {
    return ((b.y - a.y) * (c.x - b.x) -
        (b.x - a.x) * (c.y - b.y)) < 0;
}

void graham() {
    hull[0] = 0;
    hull[1] = 1;
    H = 2;

    for (int i = 2; i < N; i++) {
        while (H >= 2 &&
            !is_counter_clockwise(points[hull[H - 2]],
                points[hull[H - 1]],
                points[i])) {
            H--;
        }
        hull[H++] = i;
    }
}

int main()
{
    read();

    /// SOLVE 2 - Graham Scan (points.size() * log(points.size()))
    for (int i = 1; i < N; i++) {
        if (points[i].y < points[0].y) {
            swap(points[i], points[0]);
        }
    }

    points[0].angle = 0;

    for (int i = 1; i <= N; i++) {
        points[i].angle = atan2(points[i].y - points[0].y,
            points[i].x - points[0].x);
    }

    sort(points + 1, points + N, [](Point a, Point b) {
        return a.angle < b.angle;
        });

    graham();
    fout << H << "\n";
    for (int i = 0; i < H; i++) {
        int idx = hull[i];
        fout << fixed << setprecision(12) << points[idx].x << " ";
        fout << fixed << setprecision(12) << points[idx].y << " ";
        fout << "\n";
    }
    return 0;
}