Cod sursa(job #3300922)

Utilizator SerbanBobDubei Serban Vlad SerbanBob Data 20 iunie 2025 05:35:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define EPSILON 1e-12
#define SIZE 120001

using namespace std;

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

struct Point{
    double X, Y;
} p[SIZE], hull[SIZE];

double cross(Point A, Point B, Point C);
int comp(const void *a, const void *b);

void build(int n, int &k) {
    qsort(p, n, sizeof(Point), comp);

    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(hull[k - 2], hull[k - 1], p[i]) <= 0)
            --k;

        hull[k++] = p[i];
    }

    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(hull[k - 2], hull[k - 1], p[i]) <= 0)
            --k;

        hull[k++] = p[i];
    }

    --k;
}

int main() {
    int n, k = 0;

    fin >> n;

    for (int i = 0; i < n; ++i)
        fin >> p[i].X >> p[i].Y;

    build(n, k);

    fout << k << '\n';
    for (int i = 0; i < k; ++i)
        fout << fixed << setprecision(12) << hull[i].X << ' ' << hull[i].Y << '\n';
}

double cross(Point A, Point B, Point C) {
    return (B.X - A.X) * (C.Y - A.Y) - (B.Y - A.Y) * (C.X - A.X);
}

int comp(const void *a, const void *b) {
    Point *nouA = ((Point *) a);
    Point *nouB = ((Point *) b);

    if (nouA -> X < nouB -> X)
        return -1;

    if (nouA -> X > nouB -> X)
        return 1;

    if (nouA -> Y < nouB -> Y)
        return -1;

    if (nouA -> Y > nouB -> Y)
        return 1;

    return 0;
}