Cod sursa(job #1075543)

Utilizator toranagahVlad Badelita toranagah Data 9 ianuarie 2014 09:50:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 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;

int N;
Point points[MAX_N];
Point hull[MAX_N];
int head;

void read_input();
void solve();
void print_output();
inline double cross_product(const Point &A, const Point &B, const Point &O) {
    return ((A.x - O.x) * (B.y - O.y)) - ((A.y - O.y) * (B.x - O.x));
}

int main() {
    read_input();
    solve();
    print_output();
    return 0;
}

void read_input() {
    fin >> N;

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

void solve() {
    int pos = 1;
    for (int i = 2; i <= N; i += 1) {
        if (points[i] < points[pos]) {
            pos = i;
        }
    }
    swap(points[1], points[pos]);
    Point low = points[1];

    sort(points + 2, points + N + 1,
        [low](const Point &a, const Point &b) {
            return cross_product(a, b, low) > 0;
        }
    );

    head = 0;
    hull[++head] = points[1];
    for (int i = 2; i <= N; i += 1) {
        while (head > 2 && cross_product(points[i], hull[head], hull[head - 1]) > 0) {
            head -= 1;
        }
        hull[++head] = points[i];
    }
}

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