Cod sursa(job #1344447)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 16 februarie 2015 18:56:25
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

#define DIM 120000

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

int N, st[DIM], freq[DIM];

struct punct {
    double x, y;
}v[DIM];

double modul(double a, double b) {
    if(a - b >= 0) {
        return a - b;
    }

    return b - a;
}

int egal(double a, double b) {
    if(fabs(a - b) < 0.00000001) return 1;

    return 0;
}

bool cmp(punct a, punct b) {
    if(egal(a.x, b.x)) {
        return a.y < b.y;
    }

    return a.x < b.x;
}

int Sarrus(int i, int j, int k) {
    return ((v[i].x * v[j].y + v[j].x * v[k].y + v[k].x * v[i].y - v[i].x * v[k].y - v[j].x * v[i].y - v[k].x * v[j].y) > 0.0 ? 1 : -1);
}

int main() {
    fin >> N;

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

    sort(v + 1, v + 1 + N, cmp);

    st[++st[0]] = 1;
    st[++st[0]] = 2;
    freq[1] = freq[2] = 1;

    for(int i = 3; i <= N; i++) {
        while(st[0] >= 2 && Sarrus(st[st[0]], st[st[0] - 1], i) < 0) {
            freq[st[st[0]]] = 0;
            st[st[0]--] = 0;
        }

        st[++st[0]] = i;
        freq[i] = 1;
    }

    for(int i = N; i >= 1; --i) {
        while(freq[i] == 0 && st[0] >= 2 && Sarrus(st[st[0]], st[st[0] - 1], i) < 0) {
            freq[st[st[0]]] = 0;
            st[st[0]--] = 0;
        }

        if(freq[i] == 0) {
            st[++st[0]] = i;
            freq[i] = 1;
        }
    }

    fout << st[0] << '\n';

    for(int i = 1; i <= st[0]; ++i) {
        fout << setprecision(6) << fixed << v[st[i]].y << ' ' << fixed << v[st[i]].x << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}