Cod sursa(job #3301134)

Utilizator 13wannabedevBenczik Roberto-Patrik 13wannabedev Data 21 iunie 2025 20:38:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;

#define MAX 150005

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

int c, stack[MAX], top, start;
long double minX, minY = 1e18;

struct Point {
    long double x, y;
} points[MAX];

long double cross(const Point &O, const Point &A, const Point &B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

long double dist2(const Point &A, const Point &B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

bool cmp(const Point &a, const Point &b) {
    long double c = cross(points[0], a, b);
    if (abs(c) < 1e-12) {
        return dist2(points[0], a) < dist2(points[0], b);
    }
    return c > 0;
}

void read() {
    f >> c;
    for (int i = 0; i < c; i++) {
        f >> points[i].x >> points[i].y;
        if ((points[i].y < minY) || (abs(points[i].y - minY) < 1e-12 && points[i].x < minX)) {
            minY = points[i].y;
            minX = points[i].x;
            start = i;
        }
    }
}

void solve() {
    swap(points[0], points[start]);
    sort(points + 1, points + c, cmp);

    stack[top++] = 0;
    if (c > 1)
        stack[top++] = 1;

    for (int i = 2; i < c; i++) {
        while (top >= 2 && cross(points[stack[top - 2]], points[stack[top - 1]], points[i]) <= 1e-12) {
            top--;
        }
        stack[top++] = i;
    }
}

void print() {
    g << top << "\n";
    g << fixed << setprecision(10);
    for (int i = 0; i < top; i++) {
        g << points[stack[i]].x << " " << points[stack[i]].y << "\n";
    }
}

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