Cod sursa(job #2044403)

Utilizator danyvsDan Castan danyvs Data 21 octombrie 2017 09:51:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMAX = 120005;

struct punct {
    double x, y;
};

int n;
punct vec[NMAX];
int st[NMAX], top;
bool seen[NMAX]; // seen[i] = true, daca i este pe stiva

void read() {
    fin >> n;
    for (int i = 1; i <= n; ++ i)
        fin >> vec[i].x >> vec[i].y;
}

double F(int i, int j, int p) {
    // returneaza < 0 daca puncdtul vec[p] este in semiplanul - al dreptei determinata de puctele (vec[i], vec[j])
    return vec[p].x * (vec[i].y - vec[j].y) + vec[p].y * (vec[j].x - vec[i].x) + vec[i].x * vec[j].y - vec[j].x * vec[i].y;

}

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

void hill() {
    // algoritmul lui Hill
    sort(vec + 1, vec + n + 1, cmp);
    st[++ top] = 1;
    st[++ top] = 2;
    seen[2] = true;
    for (int i = 3; i <= n; ++ i) {
        while (top > 1 && F(st[top - 1], st[top], i) < 0) {
            seen[st[top]] = false;
            -- top;
        }
        st[++ top] = i;
        seen[i] = true;
    }
    for (int i = n - 1; i; -- i)
        if (!seen[i]) {
            while (F(st[top - 1], st[top], i) < 0) {
                seen[st[top]] = false;
                -- top;
            }
            st[++ top] = i;
            seen[i] = true;
        }
}

void print() {
    fout << top - 1 << "\n";
    for (int i = 1; i < top; ++ i)
        fout << fixed << setprecision(12) << vec[st[i]].x << " " << vec[st[i]].y << "\n";
}

int main() {
    read();
    fin.close();
    hill();
    print();
    fout.close();
    return 0;
}