Cod sursa(job #2959224)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 30 decembrie 2022 11:11:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;

struct punct {
    double x, y;
} v[120005];

double unghi(punct a, punct b, punct c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool comp(punct a, punct b) {
    return unghi(v[1], a, b) > 0;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    int start = 1;
    for (int i = 2; i <= n; ++i)
        if (v[i].y < v[start].y || (v[i].y == v[start].y && v[i].x < v[start].x))
            start = i;
    swap(v[start], v[1]);
    sort(v + 2, v + n + 1, comp);
    vector <int> s;
    s.push_back(1);
    s.push_back(2);
    for (int i = 3; i <= n; ++i) {
        while (s.size() >= 2 && unghi(v[s[s.size() - 2]], v[s.back()], v[i]) < 0)
            s.pop_back();
        s.push_back(i);
    }
    fout << s.size() << "\n";
    fout << fixed << setprecision(12);
    for (auto nr : s)
        fout << v[nr].x << " " << v[nr].y << "\n";
    return 0;
}