Cod sursa(job #2763757)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 16 iulie 2021 17:42:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

const int NMAX = 120000;

int N;
pair<long double, long double> v[NMAX + 2];

bool ccw(pair<long double, long double> A, pair<long double, long double> B, pair<long double, long double> C) {
    return (B.second - A.second) * (C.first - A.first) < (C.second - A.second) * (B.first - A.first);
}

inline bool cmp(pair<long double, long double> A, pair<long double, long double> B) {
    return ccw(v[1], A, B);
}

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> v[i].first >> v[i].second;
    }
    for(int i = 2; i <= N; i++) {
        if(v[i].second == v[1].second) {
            if(v[i].first < v[1].first) {
                swap(v[i], v[1]);
            }
        } else if(v[i].second < v[1].second) {
            swap(v[i], v[1]);
        }
    }

    sort(v + 2, v + N + 1, cmp);

    vector<pair<long double, long double>> st;
    for(int i = 1; i <= N; i++) {
        while((int)st.size() > 1 && !ccw(st[(int)st.size() - 2], st[(int)st.size() - 1], v[i])) {
            st.pop_back();
        }
        st.push_back(v[i]);
    }

    cout << (int)st.size() << '\n';
    for(int i = 0; i < (int)st.size(); i++) {
        cout << fixed << setprecision(12) << st[i].first << ' ' << st[i].second << '\n';
    }

    return 0;
}