Cod sursa(job #3365399)

Utilizator RuxandraPro12_Metehau Ruxandra Maria RuxandraPro12_ Data 20 septembrie 2026 19:24:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

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

const int NMAX = 12e4;

int n, vf;
pair <double, double> v[NMAX + 5], stiva[NMAX + 5];

double produs_vect (pair<double, double> a, pair<double, double> b, pair<double, double> c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

bool cmp (pair<double, double> A, pair<double, double> B) {
    return produs_vect(v[1], A, B) < 0;
}

int main () {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;
    int min_panta = 1;
    for (int i = 2; i <= n; i++) {
        if (v[i] < v[min_panta])
            min_panta = i;
    }
    swap(v[1], v[min_panta]);
    sort (v + 2, v + 1 + n, cmp);
    stiva[++vf] = v[1];
    stiva[++vf] = v[2];
    for (int i = 3; i <= n; i++) {
        while (vf >= 2 && produs_vect(stiva[vf - 1], stiva[vf], v[i]) > 0)
            vf--;
        stiva[++vf] = v[i];
    }
    fout << fixed << setprecision(6);
    fout << vf << "\n";
    for (int i = vf; i >= 1; i--) // invers acelor ceasornicului
        fout << stiva[i].first << " " << stiva[i].second << "\n";
    return 0;
}