Cod sursa(job #3220262)

Utilizator schema_227Stefan Nicola schema_227 Data 2 aprilie 2024 23:05:35
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMAX = 120001;

vector<pair<long double, long double>> points;

vector<pair<long double, long double>> hull1, hull2;

bool SORT(const pair<long double, long double>& a, const pair<long double, long double>& b) {
    if (a.first != b.first)
        return (a.first <= b.first);
    return (a.second <= b.second);
}

int AREA(pair<long double, long double> a, pair<long double, long double> b, pair<long double, long double> c) {
    return a.first * b.second + b.first * c.second + c.first * a.second - b.second * c.first - c.second * a.first - a.second * b.first;
}

int main() {
    int n;
    in >> n;
    for(int i = 0; i < n; i++) {
        long double x, y;
        in >> x >> y;
        points.push_back({x, y});
    }
    sort(points.begin(), points.end(), SORT);

    hull1.push_back(points[0]);
    for (int i = 1; i < points.size(); i++) {
        while (hull1.size() > 1 && AREA(hull1[hull1.size() - 1], hull1[hull1.size() - 2], points[i]) > 0) {
            hull1.pop_back();
        }
        hull1.push_back(points[i]);
    }

    hull2.push_back(points[0]);
    for (int i = 1; i < points.size(); i++) {
        while (hull2.size() > 1 && AREA(hull2[hull2.size() - 1], hull2[hull2.size() - 2], points[i]) < 0) {
            hull2.pop_back();
        }
        hull2.push_back(points[i]);
    }

    out << hull1.size() - 1 + hull2.size() - 1 << '\n';
    for(int i = 0; i < hull1.size(); i++) {
        out << fixed << setprecision(6) << hull1[i].first << " " << fixed << setprecision(6) << hull1[i].second;
        out << '\n';
    }
    for(int i = hull2.size() - 2; i >= 0; i--) {
        out << fixed << setprecision(6) << hull2[i].first << " " << fixed << setprecision(6) << hull2[i].second;
        out << '\n';
    }
    return 0;
}
/*
8
2 0
0 2
1 3
0 4
3 3
2 6
4 2
4 4
*/