Cod sursa(job #3224002)

Utilizator MAlex2019Melintioi George Alexandru MAlex2019 Data 14 aprilie 2024 12:19:48
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.92 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;
using point=pair<double,double>;

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

const int MAXN = 12e4;
point v[MAXN + 1];
point *O = v;

bool cmp2(point &A, point &B) {
    if (A.first == B.first)
        return A.second < B.second;
    return A.first < B.first;
}

bool crossProduct(point &A, point &B) {
    return A.first * B.second > A.second * B.first;
}

double cmpcrossProduct(point A, point B) {
    point AB = {O->first - A.first, O->second - A.second};
    point BC = {B.first - O->first, B.second - O->second};
    return crossProduct(AB, BC);
}

bool trigonometricOrder(point A, point B, point C) {
    point AB = {B.first - A.first, B.second - A.second};
    point BC = {C.first - B.first, C.second - B.second};
    return crossProduct(AB, BC);
}

ostream& operator<<(ostream &os, const point &a) {
    os << a.first << ' ' << a.second;
    return os;
}

int orientation(point p, point &q, point &r) {
    double val = (q.second - p.second) * (r.first - q.first) - (q.first - p.first) * (r.second - q.second);

    if (abs(val) < 1e-9) return 0; // Drepte coliniare
    return (val > 0) ? 1 : 2; // 1 pentru sens trigonometric, 2 pentru sens invers trigonometric
}

// Funcție de comparație pentru a sorta punctele în funcție de unghiul lor față de un punct de referință
bool compare(point& p1, point& p2) {
    // Considerăm un punct de referință arbitrar (0, 0)
    int o = orientation(point(0, 0), p1, p2);
    if (o == 0) {
        // Dacă sunt coliniare, sortăm după distanță
        return (p1.first * p1.first + p1.second * p1.second) < (p2.first * p2.first + p2.second * p2.second);
    }
    return (o == 1); // Sortăm în ordinea sensului trigonometric
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    int n;
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i].first >> v[i].second;
    sort(v, v + n, cmp2);
    sort(v + 1, v + n, cmpcrossProduct);

   // for (int i = 0; i < n; i++)
     //   cout << v[i] << '\n';

    vector<point> poli;
    poli.push_back(*O);
    v[n] = v[0];
    for (int i = 1; i < n; i++) {
        while (i < n && trigonometricOrder(*poli.rbegin(), v[i], v[i + 1]))
            i++;
        poli.push_back(v[i]);
        //if (i == n - 1)
          //  poli.push_back(v[n - 1]);
    }
    //for (point elem: poli)
      //  cout << elem << '\n';
    list<point> newpoli(poli.begin(), poli.end());
    while (true) {
        bool stop = true;
        auto itr = newpoli.begin();
        for (++itr; itr != newpoli.end(); itr++)
            if (trigonometricOrder(*prev(itr), *itr, *next(itr))) {
                itr = prev(newpoli.erase(itr));
                stop = false;
            }
        if (stop)
            break;
    }
    // while (true) {
    //     bool stop = true;
    //     for (int i = 1; i < poli.size() - 1; i++)
    //         if (trigonometricOrder(poli[i - 1], poli[i], poli[i + 1])) {
    //             for (int j = i; j < poli.size() - 1; j++)
    //                 poli[j] = poli[j + 1];
    //             poli.resize(poli.size() - 1);
    //             i--;
    //             stop = false;
    //         }
    //     if (stop)
    //         break;
    // }

    //sort(poli.begin(), poli.end(), compare);
    poli = vector<point>(make_move_iterator(begin(newpoli)), make_move_iterator(end(newpoli)));
    reverse(poli.begin() + 1, poli.end());
    /*while (poli[0].second > poli[1].second) {
        point aux = poli[0];
        for (int i = 0; i < poli.size() - 1; i++)
            poli[i] = poli[i + 1];
        poli[poli.size() - 1] = aux;
    }*/

    fout << poli.size() << '\n';
    for (point elem: poli)
        fout << fixed << setprecision(14) << elem << '\n';

    return 0;
}