Cod sursa(job #3301110)

Utilizator 13wannabedevBenczik Roberto-Patrik 13wannabedev Data 21 iunie 2025 19:08:27
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <iostream>

#define MAX 100099
#define W 1000000000.0

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

typedef struct Point {
    double x, y, deg;
};

Point points[MAX], o = {W, W, 0.0}, stack[MAX];
int n, dim = 0;

double calc(Point a, Point b) {
    return atan2(a.y - b.y, a.x - b.x);
}

bool checkOrigin(Point p) {
    if (p.y < o.y)
        return true;
    if (p.y == o.y && p.x < o.x)
        return true;
    return false;
}

bool cmp(Point a, Point b) {
    if (a.deg == b.deg) {
        double d1 = (a.x - o.x) * (a.x - o.x) + (a.y - o.y) * (a.y - o.y);
        double d2 = (b.x - o.x) * (b.x - o.x) + (b.y - o.y) * (b.y - o.y);
        return d1 > d2;
    }
    return a.deg < b.deg;
}

bool left(Point a, Point b, Point c) {
    double prd = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return prd > 0;
}

void read() {
    f >> n;

    for (int i = 0; i < n; i++) {
        f >> points[i].x >> points[i].y;
        points[i].deg = 0.0;
        if (checkOrigin(points[i])) {
            o = points[i];
        }
    }

    for (int i = 0; i < n; i++) {
        points[i].deg = calc(points[i], o);
    }

    sort(points, points + n, cmp);

    int j = 0;
    for (int i = 1; i < n; i++) {
        if (fabs(points[i].deg - points[j].deg) > 1e-9) {
            points[++j] = points[i];
        } else {
            double d1 = (points[i].x - o.x) * (points[i].x - o.x) + (points[i].y - o.y) * (points[i].y - o.y);
            double d2 = (points[j].x - o.x) * (points[j].x - o.x) + (points[j].y - o.y) * (points[j].y - o.y);
            if (d1 > d2) {
                points[j] = points[i];
            }
        }
    }
    n = j + 1;
}

void print(Point p) {
    g << fixed << setprecision(6) << p.x << " " << p.y << '\n';
}

void solve() {
    stack[0] = points[0];
    dim = 1;

    if (n > 1) {
        stack[1] = points[1];
        dim++;
    }

    for (int i = 2; i < n; i++) {
        while (dim >= 2 && !left(stack[dim - 2], stack[dim - 1], points[i])) {
            dim--;
        }
        stack[dim++] = points[i];
    }

    g << dim << '\n';
    for (int i = 0; i < dim; i++) {
        print(stack[i]);
    }
}

int main() {
    read();
    solve();
    return 0;
}