Cod sursa(job #1168803)

Utilizator mihai995mihai995 mihai995 Data 9 aprilie 2014 17:19:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

const int N = 1e5;
const bool supportLine = false, medianLine = true;

struct Point{
    double x, y;

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

    inline Point operator-(const Point P) const {
        return Point(x - P.x, y - P.y);
    }

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

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

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

ofstream out("rubarba.out");

inline long long crossProduct(Point A, Point B, Point C){
    return (B - A) * (C - A);
}

int getConvexHull(Point P[], int nrP){
    sort(P, P + nrP);

    int hullSize = 0;
    for (int i = 0 ; i < nrP ; i++){
        while ( hullSize > 1 && crossProduct(hull[hullSize - 2], hull[hullSize - 1], P[i]) <= 0 )
            hullSize--;
        hull[ hullSize++ ] = P[i];
    }
    int capSize = hullSize;
    for (int i = nrP - 2 ; i >= 0 ; i--){
        while ( hullSize > capSize && crossProduct(hull[hullSize - 2], hull[hullSize - 1], P[i]) >= 0 )
            hullSize--;
        hull[ hullSize++ ] = P[i];
    }
    hullSize--;
    for (int i = 0 ; i < hullSize ; i++)
        P[i] = hull[i];
    return hullSize;
}

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

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

    nrP = getConvexHull(P, nrP);

    ofstream out("infasuratoare.out");

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

    return 0;
}