Cod sursa(job #2737192)

Utilizator trifangrobertRobert Trifan trifangrobert Data 4 aprilie 2021 15:11:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define mp make_pair
#define pdd pair <double, double>

using namespace std;

double det(pdd a, pdd b, pdd c) {
    double res = 0;
    res += a.first * b.second;
    res += b.first * c.second;
    res += c.first * a.second;
    res -= b.second * c.first;
    res -= c.second * a.first;
    res -= a.second * b.first;
    return res;
}

vector <pdd> ConvexHull(vector <pdd> p) {
    vector <pdd> stk;
    for (int i = 0; i < p.size(); ++i) {
        while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), p[i]) < 0)
            stk.pop_back();
        stk.push_back(p[i]);
    }
    return stk;
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int N;
    fin >> N;
    vector <pdd> points(N);
    for (int i = 0; i < N; ++i) {
        fin >> points[i].first >> points[i].second;
    }
    sort(points.begin(), points.end());
    vector <pdd> underPoints, overPoints;
    underPoints.push_back(points[0]);
    overPoints.push_back(points[0]);
    for (int i = 1; i < N - 1; ++i) {
        if (det(points[0], points[i], points.back()) >= 0) {
            underPoints.push_back(points[i]);
        }
        else {
            overPoints.push_back(points[i]);
        }
    }
    underPoints.push_back(points.back());
    overPoints.push_back(points.back());
    reverse(overPoints.begin(), overPoints.end());
    vector <pdd> hullUnder = ConvexHull(underPoints);
    vector <pdd> hullOver = ConvexHull(overPoints);
    hullUnder.pop_back();
    hullOver.pop_back();
    vector <pdd> hull;
    for (auto& i : hullUnder)
        hull.push_back(i);
    for (auto& i : hullOver)
        hull.push_back(i);
    fout << hull.size() << "\n";
    fout << setprecision(12) << fixed;
    for (auto& i : hull) {
        fout << i.first << " " << i.second << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}