Cod sursa(job #1106787)

Utilizator toranagahVlad Badelita toranagah Data 13 februarie 2014 10:23:26
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

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

#define x first
#define y second
typedef pair<double, double> Point;

const int MAX_N = 120100;
const double EPS = 1e-12;

int N;
Point p[MAX_N];
int hull[MAX_N];
bool used[MAX_N];
int head;

void convex_hull();
double cross_product(int o, int a, int b);

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

    convex_hull();

    fout << setprecision(9);
    fout << head << '\n';
    for (int i = 1; i <= head; i += 1) {
        fout << p[hull[i]].x << ' ' << p[hull[i]].y << '\n';
    }
}

void convex_hull() {
    sort(p + 1, p + N + 1);

    hull[1] = 1;
    hull[2] = 2;
    head = 2;
    used[2] = true;

    for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
        if (used[i]) continue;
        while (head >= 2 && cross_product(hull[head - 1], hull[head], i) < EPS) {
            used[hull[head--]] = false;
        }
        used[i] = true;
        hull[++head] = i;
    }
    head -= 1;
}

inline double cross_product(int o, int a, int b) {
    return (p[a].x - p[o].x) * (p[b].y - p[o].y) -
           (p[a].y - p[o].y) * (p[b].x - p[o].x);
}