Cod sursa(job #2060519)

Utilizator CammieCamelia Lazar Cammie Data 8 noiembrie 2017 13:04:15
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

#define MAXN 120007

using namespace std;

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

int N, nn, s[MAXN], cont;
bool ok[MAXN];

struct punct{
    double x, y;
};

punct v[MAXN];

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

inline void Read() {
    fin >> N;

    for (int i = 1; i <= N; i++) {
        fin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + N + 1, cum);
}

///ok[i] = 1 - elementul i apare in stiva

inline double semn(punct p1, punct p2, punct p3) {
    double vall = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - (p3.x * p2.y + p1.x * p3.y + p2.x * p1.y));
    return vall;
}

inline void Solve() {
    s[1] = 1; s[2] = 2; nn = 2; int ii = 2;
    double val;
    cont = 1;///parcurg elementele
    ok[2] = 1;

    while (!ok[1]) {
        while (ok[ii]) {
            if (ii == N)
                 cont *= -1;
            ii += cont;
        }

        do {
            val = 0;
            if (nn < 2) {
                s[++nn] = ii;
                break;
            }
            else {
                val = semn(v[s[nn - 1]], v[s[nn]], v[ii]);

                if (val < 0)
                    s[++nn] = ii,
                    ok[ii] = 1;
                else if (val > 0) {
                    ok[s[nn]] = 0;
                    nn--;
                }
                else
                    ii++;
            }
        } while (val > 0);
    }
}

inline void Write() {
    fout << nn - 1 << "\n";
    for (int i = nn; i > 1; i--)
        fout << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
}

int main () {
    Read();
    Solve();
    Write();

    fin.close(); fout.close(); return 0;
}