Cod sursa(job #3310226)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 12 septembrie 2025 10:30:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <ios>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;
struct Punct {
    double x, y;
    Punct operator-(const Punct &p) const {
        return {x - p.x, y - p.y};
    }
    Punct operator+(const Punct &p) const {
        return {x + p.x, y + p.y};
    }
    Punct operator*(double t) const {
        return {x * t, y * t};
    }
    double operator^(const Punct &p) const {
        return x*p.y - y*p.x;
    }
};

vector<Punct> infasuratoare(vector<Punct> poligon) {
    map<double, Punct> p;
    int imn;
    Punct mn{10e12, 10e12};
    for(int i=0; i<poligon.size(); ++i) {
        auto &punct = poligon[i];
        if(punct.y < mn.y || (punct.y == mn.y && punct.x < mn.x)) {
            mn = punct;
            imn = i;
        }
    }
    for(int i=0; i<poligon.size(); ++i) {
        auto &punct = poligon[i];
        if(imn != i) {
            double unghi = atan2(punct.y-mn.y, punct.x-mn.x);
            if(!p.count(unghi)) {
                p[unghi] = punct;
            } else {
                double d1 = (p[unghi].x-mn.x)*(p[unghi].x-mn.x) + (p[unghi].y-mn.y)*(p[unghi].y-mn.y);
                double d2 = (punct.x-mn.x)*(punct.x-mn.x) + (punct.y-mn.y)*(punct.y-mn.y);
                if(d2 > d1) {
                    p[unghi] = punct;
                }
            }
        }
    }

    vector<Punct> stiva;
    stiva.push_back(mn);

    for(auto &[unghi, punct] : p) {
        while(stiva.size() >= 2) {
            Punct A = stiva[stiva.size()-2];
            Punct B = stiva[stiva.size()-1];
            long double k = (B.x - A.x)*(punct.y - A.y) - (B.y - A.y)*(punct.x - A.x);
            if(k <= 0) {
                stiva.pop_back();
            } else {
                break;
            }
        }
        stiva.push_back(punct);
    }

    return stiva;
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fout << fixed << setprecision(6);
    int N;
    fin >> N;
    vector<Punct> pt(N);
    for(int i=0; i<N; ++i) {
        fin >> pt[i].x >> pt[i].y;
    }
    auto cpt = infasuratoare(pt);
    fout << cpt.size() << '\n';
    for(auto p: cpt) {
        fout << p.x << ' ' << p.y << '\n';
    }
    return 0;
}