Cod sursa(job #2849316)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 14 februarie 2022 21:03:36
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define cin in
#define cout out
#endif // LOCAL

typedef double data_t;
constexpr data_t EPS = 0.8e-12;
constexpr data_t PI = 3.1415926535897932384626433832795;
pair<data_t, data_t> avg;

bool cmp(pair<data_t, data_t> a, pair<data_t, data_t> b) {
    data_t angle_a = atan2(a.second - avg.second, a.first - avg.first);
    if(angle_a <= 0) angle_a += 2 * PI;

    data_t angle_b = atan2(b.second - avg.second, b.first - avg.first);
    if(angle_b <= 0) angle_b += 2 * PI;

    return angle_a <= angle_b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<pair<data_t, data_t>> pts(n);
    for(auto &e : pts) cin >> e.first >> e.second;
    sort(pts.begin(), pts.end());

    vector<bool> chosen(n, false);

    {
        // From left to right
        data_t range_l = pts[0].second, range_r = pts[0].second;
        chosen[0] = true;

        for(int i = 1; i < n; i++) {
            if(pts[i].second < range_l) {
                range_l = pts[i].second;
                chosen[i] = true;
            }
            if(pts[i].second > range_r) {
                range_r = pts[i].second;
                chosen[i] = true;
            }
        }
    }

    {
        // From right to left
        data_t range_l = pts[n - 1].second, range_r = pts[n - 1].second;
        chosen[n - 1] = true;

        for(int i = n - 1; i >= 0; i--) {
            if(pts[i].second < range_l) {
                range_l = pts[i].second;
                chosen[i] = true;
            }
            if(pts[i].second > range_r) {
                range_r = pts[i].second;
                chosen[i] = true;
            }
        }
    }

    vector<pair<data_t, data_t>> hull;
    for(int i = 0; i < n; i++) {
        if(chosen[i]) {
            hull.push_back(pts[i]);
            avg.first += pts[i].first;
            avg.second += pts[i].second;
        }
    }
    avg.first  /= static_cast<data_t>(hull.size());
    avg.second /= static_cast<data_t>(hull.size());

    sort(hull.begin(), hull.end(), cmp);

    cout << hull.size() << endl;
    for(auto e : hull)
        cout << fixed << setprecision(10) << e.first << " " << e.second << endl;
}