Cod sursa(job #1810155)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 19 noiembrie 2016 17:43:33
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 N = 120100;

int i, n, s[N], k;
bool viz[N];

struct el {
    double x,y;
} v[N];

long double cm(el A, el B) {
    if (A.x != B.x) {
        return A.x>B.x;
    }
    return A.y<B.y;
}

inline long double det(int i, int j, int k) {
    return 1.0*v[i].x*v[j].y+v[j].x*v[k].y+v[i].y*v[k].x-v[i].y*v[j].x-v[j].y*v[k].x-v[i].x*v[k].y;
}

int main() {
    fin >> n;
    for (i = 1; i <= n; ++i) {
        fin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cm);
    viz[2] = 1;
    s[1] = 1;
    s[2] = 2;
    k = 2;
    for (i = 3; i <= n; ++i) {
        if (det(s[k - 1], s[k], i) < 0) {
            s[++k] = i;
            viz[i] = 1;
        } else {
            while (det(s[k - 1], s[k], i) >= 0 && k > 1){
                viz[s[k]] = 0;
                s[k] = 0;
                k--;
            }
            s[++k] = i;
            viz[i] = 1;
        }
    }
    for (i = n - 1; i >= 1; --i) {
        if (!viz[i]) {
            if (det(s[k - 1], s[k], i) < 0) {
                s[++k] = i;
                viz[i] = 1;
            } else {
                while (det(s[k - 1], s[k], i) >= 0 && k > 1) {
                    viz[s[k]] = 0;
                    s[k] = 0;
                    k--;
                }
                s[++k] = i;
                viz[i] = 1;
            }
        }
    }
    fout << k - 1 << "\n";
    k--;
    for (i = k - 1; i > 0; --i)
        fout << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y <<"\n";
    fout << v[s[k]].x << " " << v[s[k]].y << "\n";
    return 0;
}