Cod sursa(job #934569)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 30 martie 2013 19:49:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long int64;
typedef vector<int>::iterator it;
typedef pair<double, double> Point;

const int oo = 0x3f3f3f3f;
const int MAX_N = 120005;
const double Eps = 1e-9;

vector<Point> Points, Hull;

inline double Det(const Point& A, const Point& B, const Point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

vector<Point> ConvexHull(vector<Point>& points) {
    int n = static_cast<int>(points.size());
    vector<int> stack = vector<int>(n + 2, 0);
    vector<bool> used = vector<bool>(n, false);
    sort(points.begin(), points.end());
    stack[++stack[0]] = 0;
    for (int i = 1, p = 1; i >= 0; i += (p = (i == n - 1 ? -p : p))) {
        if (used[i])
            continue;
        while (stack[0] > 1 && Det(points[stack[stack[0] - 1]], points[stack[stack[0]]], points[i]) < Eps)
            used[stack[stack[0]--]] = false;
        used[stack[++stack[0]] = i] = true;
    }
    vector<Point> hull;
    for (int i = 1; i < stack[0]; ++i)
        hull.push_back(points[stack[i]]);
    return hull;
}

void Solve() {
}

void Read() {
    ifstream in("infasuratoare.in");
    int N; in >> N;
    for (int i = 1; i <= N; ++i) {
        Point newPoint; in >> newPoint.x >> newPoint.y;
        Points.push_back(newPoint);
    }
    in.close();
}

void Print() {
    ofstream out("infasuratoare.out");
    out << Hull.size() << "\n";
    for (size_t i = 0; i < Hull.size(); ++i)
        out << fixed << setprecision(8) << Hull[i].x << " " << Hull[i].y << "\n";
    out.close();
}

int main() {
    Read();
    Hull = ConvexHull(Points);
    Print();
    return 0;
}