Cod sursa(job #2809750)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 27 noiembrie 2021 15:25:50
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
// complexitate O(Nlog2N), data de sortare
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

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

const int N = 1.2e5 + 1;
int n, punct_initial = 1, varf;
pair<double, double> p[N], stiva[N];

inline int produsIncrucisat(pair<double, double> A, pair<double, double> B, pair<double, double> C){
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); // valoarea componentei pe axa z a lui AB X AC
}

inline bool cmp(pair<double, double> p1, pair<double, double> p2){
    return produsIncrucisat(p[1], p1, p2) < 0; // < 0 <=> vectorul (originea in p[1]) cu capatul p2 e in dreapta celui cu capatul p1 (daca consideram axa centrala vectorul cu capatul in p1, p2 e in dreapta lui p1)
}

int main(){
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> p[i].x >> p[i].y;

    f.close();
    for(int i = 2; i <= n; i++){
        if(p[i] < p[punct_initial]) // punctul cel mai din stanga si, in caz de egalitate, cel mai de jos
            punct_initial = i;
    }

    swap(p[1], p[punct_initial]);
    sort(p + 2, p + n + 1, cmp);
    /*
     *  punctele sunt sortate dupa semnul componentei z din produsul incrucisat al vectorilor cu capete in puncte si originea in p[1]
     *  astfel, punctele de la inceput au putine (sau chiar 0) puncte a caror vector sa se afle in stanga lor
     *  iar punctele spre sfarsit au multe (chiar toate)
     *  altfel, punctele sunt sortate in functie de unghiul pe care il fac cu originea unui sistem de axe interschimbate (X interschimbat cu Y), avandu-l in centru pe p[1]
     *  adica unghiul creste din stanga spre dreapta, invers trigonometric
     */
    stiva[1] = p[1];
    stiva[2] = p[2];
    varf = 2;
    for(int i = 3; i <= n; i++){
        while(varf >= 2 && produsIncrucisat(stiva[varf - 1], stiva[varf], p[i]) > 0) // > 0 <=> vectorul lui p[i] (cu originea in stiva[varf - 1] si capatul in p[i]) se afla in stanga celui lui stiva[varf]
            varf--;

        stiva[++varf] = p[i];
    }

    g << varf << '\n';
    for(int i = varf; i >= 1; i--) // ordinea 1 ... varf este cea a acelor de ceasornic; noua ne trebuie ordinea trigonometrica
        g << fixed << setprecision(9) << stiva[i].x << ' ' << stiva[i].y << '\n';

    g.close();
}