Cod sursa(job #2044402)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 21 octombrie 2017 09:51:16
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 120005;

struct Point{
    double x, y;
};

inline bool Compare(Point A, Point B) {
    return (A.y == B.y) ? A.y < B.y : A.x < B.x;
}

Point a[nMax];
int n, st[nMax], top;
bool used[nMax];

double F(int i, int j, int p) {
    /**
    *   Semnul numarului returnat determina semiplanul in care
    *   se afla punctul p in raport cu dreapta
    **/
    return a[p].x * (a[i].y - a[j].y) +
           a[p].y * (a[j].x - a[i].x) +
           a[i].x * a[j].y - a[j].x * a[i].y;
    /**
    *   < 0 inseamna planul -
    *   > 0 inseamna planul +
    *   = 0 inseamna coliniaritate
    **/
}

void Read() {
    ifstream fin ("infasuratoare.in");
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i].x >> a[i].y;
    }
    fin.close();
}

void Hill() {
    sort(a + 1, a + n + 1, Compare);
    st[1] = 1;
    st[2] = 2;
    used[1] = used[2] = 1;
    top = 2;
    for (int i = 3; i <= n; i++) {
        while (top > 1 && F(st[top - 1], st[top], i) < 0) {
            used[st[top]] = 0;
            top--;
        }
        st[++top] = i;
        used[i] = 1;
    }
    used[1] = 0;
    for (int i = n - 1; i >= 1; i--) {
        if (used[i] == 0) {
            while (F(st[top - 1], st[top], i) < 0) {
            used[st[top]] = 0;
            top--;
            }
            st[++top] = i;
            used[i] = 1;
        }
    }
}

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

int main() {
    Read();
    Hill();
    Write();
    return 0;
}