Cod sursa(job #3357691)

Utilizator Andrei_GhiocelAndrei Tiberiu Ghiocel Andrei_Ghiocel Data 12 iunie 2026 20:57:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Punct {
    double x, y;

    bool operator<(const Punct& altul) const {
        if (x != altul.x) {
            return x < altul.x;
        }
        return y < altul.y;
    }
};

double determinant(const Punct& O, const Punct& A, const Punct& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");

    int nrPuncte;
    if (!(fin >> nrPuncte)) return 0;

    vector<Punct> puncte(nrPuncte);
    for (int i = 0; i < nrPuncte; ++i) {
        fin >> puncte[i].x >> puncte[i].y;
    }

    sort(puncte.begin(), puncte.end());//o foloim pe asta predefinita

    vector<Punct> infasuratoareJos;
    for (int i = 0; i < nrPuncte; ++i) {
        while (infasuratoareJos.size() >= 2 && determinant(infasuratoareJos[infasuratoareJos.size() - 2], infasuratoareJos.back(), puncte[i]) <= 1e-11) {
            infasuratoareJos.pop_back();
        }
        infasuratoareJos.push_back(puncte[i]);
    }

    vector<Punct> infasuratoareSus;
    for (int i = nrPuncte - 1; i >= 0; --i) {
        while (infasuratoareSus.size() >= 2 && determinant(infasuratoareSus[infasuratoareSus.size() - 2], infasuratoareSus.back(), puncte[i]) <= 1e-11) {
            infasuratoareSus.pop_back();
        }
        infasuratoareSus.push_back(puncte[i]);
    }

    infasuratoareJos.pop_back();
    infasuratoareSus.pop_back();

    vector<Punct> poligonRezultat;
    poligonRezultat.insert(poligonRezultat.end(), infasuratoareJos.begin(), infasuratoareJos.end());
    poligonRezultat.insert(poligonRezultat.end(), infasuratoareSus.begin(), infasuratoareSus.end());

    fout << poligonRezultat.size() << "\n";
    fout << fixed << setprecision(6);
    for (const auto& punct : poligonRezultat) {
        fout << punct.x << " " << punct.y << "\n";
    }

    return 0;
}