Cod sursa(job #3301132)

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

#define MAX 190000

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

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

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

bool cmp(const Point &a, const Point &b) {
    return a.x * b.y >= b.x * a.y;
}

bool check(Point a, Point b, Point c) {
    long double cross = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
    return cross > 0;
}

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

    for (int i = 0; i < c; i++) {
        points[i].x -= minX;
        points[i].y -= minY;
    }
}

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

    stack[top++] = 0;
    stack[top++] = 1;

    for (int i = 2; i < c; i++) {
        while (top >= 2 && !check(
                               points[stack[top - 2]],
                               points[stack[top - 1]],
                               points[i])) {
            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 + minX << " "
          << points[stack[i]].y + minY << "\n";
    }
}

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