Cod sursa(job #1780115)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 15 octombrie 2016 20:55:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;
typedef double f64;

const int SPQR = 120005;
const f64 EPS = 1e-16;

struct PTX {
    f64 x, y;

    void rot(double alpha) {
        f64 _x = x * cos(alpha) - y * sin(alpha);
        f64 _y = x * sin(alpha) + y * cos(alpha);
        x = _x;
        y = _y;
    }

    bool operator < (const PTX &arg) const {
        return (abs(x-arg.x)<EPS) ? (y < arg.y) : (x < arg.x);
    }
};

//PTX pts[SPQR];
//bool gws[SPQR];
//vector<pair<PTX, PTX> > vag[SPQR];

f64 ccw(const PTX &a, const PTX &b, const PTX &c) {
    return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
}

vector<PTX> make_hull(vector<PTX> ptr) {
    vector<PTX> hull, ue, le;

    sort(ptr.begin(), ptr.end());

    for(int i=0; i<ptr.size(); ++i) {
        while(ue.size()>=2 && ccw(ue[ue.size()-2], ue[ue.size()-1], ptr[i])>EPS)
            ue.pop_back();
        while(le.size()>=2 && ccw(le[le.size()-2], le[le.size()-1], ptr[i])<-EPS)
            le.pop_back();
        ue.push_back(ptr[i]);
        le.push_back(ptr[i]);
    }
    for(int i=0; i<ue.size(); ++i)
        hull.push_back(ue[i]);
    for(int i=le.size()-2; i>0; --i)
        hull.push_back(le[i]);

    return hull;
}

vector<PTX> pts, hull;
int main(void) {
    ifstream fi("infasuratoare.in");
    ofstream fo("infasuratoare.out");
    int n;

    fi >> n;
    pts.resize(n);
    for(int i=0; i<n; ++i) {
        fi >> pts[i].x >> pts[i].y;
//        pts[i].rot(acos(-1) / 7);
    }

    hull = make_hull(pts);
    fo << hull.size() << '\n';
    fo << setprecision(6) << fixed;
    for(auto i: hull)
        fo << i.x << ' ' << i.y << '\n';


    return 0;
}