Cod sursa(job #2502894)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 1 decembrie 2019 19:40:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;
struct punct {
    double x, y;
} v[240005];

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;
    }
    sort(v + 1, v + N + 1, cmp);
    for (int i = N + 1; i < 2 * N; i++) {
        v[i] = v[2 * N - i];
    }
    S.push(v[1]);
    S.push(v[2]);
    for (int i = 3; i < 2 * N; i++) {
        punct a = S.top();
        S.pop();
        while (Delta(S.top(), a, v[i]) <= 0 && S.size() > 1) {
            a = S.top();
            S.pop();
        }
        if (Delta(S.top(), a, v[i]) >= 0) {
            S.push(a);
            S.push(v[i]);
        } else S.push(v[i]);
    }
    int ct=0;
    while (!S.empty()) {
        ct++;
        sol[ct]=S.top();
        S.pop();
    }
    fout<<ct<<"\n";
    for(int i=ct;i>=1;i--)
    {
        fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y;
        fout<<"\n";
    }
}