Cod sursa(job #1198483)

Utilizator mihai995mihai995 mihai995 Data 15 iunie 2014 19:54:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

const int N = 1 + 1.2e5;

struct Point{
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}

    inline double cross(const Point& P) const {
        return x * P.y - y * P.x;
    }

    inline double cross(const Point& A, const Point& B) const {
        return cross(A) + A.cross(B) - cross(B);
    }

    inline bool operator<(const Point& P) const {
        if (x != P.x)
            return x < P.x;
        return y < P.y;
    }
};

Point P[N], aux[N];
int nrP;

void convexHull(Point P[], int& n){
    sort(P + 1, P + n + 1);

    int size = 0;
    for (int i = 1, inc = 1 ; i ; i += inc){
        while ( size > 1 && aux[ size - 1 ].cross( aux[size], P[i] ) < 0 )
            size--;
        aux[++size] = P[i];
        if (i == n) inc = -1;
    }
    n = size - 1;
    for (int i = 1 ; i <= n ; i++)
        P[i] = aux[i];
}

int main(){
    ifstream in("infasuratoare.in");

    in >> nrP;
    for (int i = 1 ; i <= nrP ; i++)
        in >> P[i].x >> P[i].y;
    in.close();

    convexHull(P, nrP);

    ofstream out("infasuratoare.out");

    out << nrP << '\n';
    out << setprecision(6) << fixed;
    for (int i = 1 ; i <= nrP ; i++)
        out << P[i].x << ' ' << P[i].y << '\n';
    out.close();

    return 0;
}