Cod sursa(job #3300983)

Utilizator coro19Vlad Coroban coro19 Data 20 iunie 2025 16:48:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <stack>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double etalon_x, etalon_y;
struct Point {
    double x, y;
    bool operator<(const Point& b) const {
        double dx1 = x - etalon_x;
        double dy1 = y - etalon_y;
        double dx2 = b.x - etalon_x;
        double dy2 = b.y - etalon_y;
        double cross = dx1 * dy2 - dy1 * dx2;
        if (cross != 0)
            return cross > 0;
        double d1 = dx1 * dx1 + dy1 * dy1;
        double d2 = dx2 * dx2 + dy2 * dy2;
        return d1 < d2;
    }
};
Point p[120005];
int n, indice;
int convexitate(const Point& a, const Point& b, const Point& c) {
    double dx1 = b.x - a.x;
    double dy1 = b.y - a.y;
    double dx2 = c.x - a.x;
    double dy2 = c.y - a.y;
    double cross = dx1 * dy2 - dy1 * dx2;
    return cross > 0;
}
int main() {
    fin>>n;
    etalon_x = 1e308;
    etalon_y = 1e308;
    for (int i = 0; i < n; ++i) {
        fin>>p[i].x>>p[i].y;
        if (p[i].x < etalon_x || (p[i].x == etalon_x && p[i].y < etalon_y)) {
            etalon_x = p[i].x;
            etalon_y = p[i].y;
            indice = i;
        }
    }
    swap(p[0],p[indice]);
    sort(p+1,p+n);
    stack<Point> stiva,stiva2;
    stiva.push(p[0]);
    stiva.push(p[1]);
    for (int i = 2; i < n; ++i) {
        while (stiva.size() >= 2) {
            Point p1 = stiva.top();
            stiva.pop();
            Point p2 = stiva.top();
            if (convexitate(p2, p1, p[i])) {
                stiva.push(p1);
                break;
            }
        }
        stiva.push(p[i]);
    }
    fout << stiva.size() << "\n" << setprecision(6) << fixed;
    while (!stiva.empty()) {
        Point p2 = stiva.top();
        stiva.pop();
        stiva2.push(p2);
    }
    //afisare- stiva strica ordinea
    while (!stiva2.empty()) {
        Point p3 = stiva2.top();
        stiva2.pop();
        fout << p3.x << " " << p3.y << "\n";
    }
    return 0;
}