Cod sursa(job #1377678)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 5 martie 2015 23:40:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

const int kNMax = 120010;
struct element {double x, y;} Punct[kNMax], Stack[kNMax];
int n, nr_elem;

void Citire() {
    ifstream in ("infasuratoare.in");
    int aux = 1;
    in >> n;
    for (int i = 1; i <= n; ++i) {
        in >> Punct[i].x >> Punct[i].y;
        if ((Punct[i].x < Punct[aux].x) || (Punct[i].x == Punct[aux].x && Punct[i].y < Punct[aux].y))
            aux = i;
    }
    swap(Punct[1], Punct[aux]);
    in.close();
}

bool Cmp(element A, element B) {
    return (((A.x - Punct[1].x) * (B.y - Punct[1].y) - (A.y - Punct[1].y) * (B.x - Punct[1].x)) >0);
}

void Solve() {
    sort(Punct + 2, Punct + n + 1, Cmp);
    Stack[++nr_elem] = Punct[1];
    Stack[++nr_elem] = Punct[2];
    for (int i = 3; i <= n; ++i) {
        while ((nr_elem >= 2) && ((Stack[nr_elem].x - Stack[nr_elem - 1].x) * (Punct[i].y - Stack[nr_elem - 1].y) - (Stack[nr_elem].y - Stack[nr_elem - 1].y) * (Punct[i].x - Stack[nr_elem - 1].x)) < 0)
            nr_elem--;
        Stack[++nr_elem] = Punct[i];
    }
}

void Afisare() {
    ofstream out("infasuratoare.out");
    out << nr_elem << '\n';
    for (int i = 1; i <= nr_elem; ++i)
        out << fixed << setprecision(6) << Stack[i].x << ' ' << Stack[i].y << '\n';
    out.close();
}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}