Cod sursa(job #2502912)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 1 decembrie 2019 20:14:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <stack>
#include <iomanip>

using namespace std;
struct punct {
    double x, y;
    int poz;
} v[240005];
bool viz[120005];

inline bool cmp(punct A, punct B) {
    if (A.x == B.x)return A.y < B.y;
    else return A.x < B.x;
}

double Delta(punct A, punct B, punct C) {
    return B.x * C.y + C.x * A.y + A.x * B.y - B.x * A.y - C.x * B.y - A.x * C.y;
}

stack<punct> S;
int N;
punct sol[120005];

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin >> N;
    for (int i = 1; i <= N; i++) {
        fin >> v[i].x >> v[i].y;
        v[i].poz = i;
    }
    sort(v + 1, v + N + 1, cmp);
    for (int i = N + 1; i < 2 * N; i++) {
        v[i] = v[2 * N - i];
    }
    //for (int i = 1; i < 2 * N; i++)
    // cout << v[i].x << " " << v[i].y << "\n";
    S.push(v[1]);
    S.push(v[2]);
    viz[v[1].poz] = 0;
    viz[v[2].poz] = 1;
    for (int i = 3; i < 2 * N; i++) {
        if (viz[v[i].poz] == 0) {
            punct a = S.top();
            viz[a.poz] = 0;
            S.pop();
            while (Delta(S.top(), a, v[i]) <= 0 && S.size() > 1) {
                a = S.top();
                viz[a.poz] = 0;
                S.pop();
            }
            if (Delta(S.top(), a, v[i]) > 0) {
                S.push(a);
                S.push(v[i]);
                viz[a.poz] = 1;
                viz[v[i].poz] = 1;
            } else {
                viz[v[i].poz] = 1;
                S.push(v[i]);
            }
            //cout << i << " * " << S.size() << "\n";
        }
    }
    int ct = 0;
    while (!S.empty()) {
        ct++;
        sol[ct] = S.top();
        S.pop();
    }
    fout << ct-1 << "\n";
    for (int i = ct; i >= 2; i--) {
        fout << fixed << setprecision(6) << sol[i].x << " " << sol[i].y;
        fout << "\n";
    }
}