Cod sursa(job #1336910)

Utilizator retrogradLucian Bicsi retrograd Data 8 februarie 2015 13:59:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<limits>
#include<iomanip>

using namespace std;
typedef double var;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const var INF = numeric_limits<var>::max();

struct Point {
    var x, y;
    Point(var a, var b) {
        x = a;
        y = b;
    }
    Point() {}
};

Point l;

var angle(Point &p, Point &q) {
    var &x1 = p.x, &y1 = p.y;
    var &x2 = q.x, &y2 = q.y;

    if(x1 == x2) {
        if(y1 < y2) return INF;
        else return -INF;
    } else {
        return (y2 - y1) / (x2 - x1);
    }
}

bool cmp(Point p, Point q) {
    return angle(l, p) < angle(l, q);
}

var crossprod(Point &p, Point &q, Point &r) {

    var &x1 = p.x, &y1 = p.y;
    var &x2 = q.x, &y2 = q.y;
    var &x3 = r.x, &y3 = r.y;

    // | i   ,  j   , k|
    // |x2-x1, y2-y1, 0|
    // |x3-x1, y3-y1, 0|

    return (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);

}

int main() {
    int n;
    var x, y;
    vector<Point> POINTS;

    l = Point(INF, 0);
    fin>>n;
    POINTS.resize(n);
    for(int i=0; i<n; i++) {
        fin>>x>>y;
        POINTS[i] = Point(x, y);

        if(l.x > x)
            l = POINTS[i];
    }

    sort(POINTS.begin(), POINTS.end(), cmp);

    vector<Point> SOL;
    SOL.push_back(l);

    for(int i=1; i<n; i++) {
        while(SOL.size() > 1 && crossprod( *(SOL.end() - 2), *(SOL.end() - 1), POINTS[i]) < 0)
            SOL.pop_back();
        SOL.push_back(POINTS[i]);
    }

    fout << SOL.size() << '\n';

    for(vector<Point>::iterator it = SOL.begin(); it != SOL.end(); ++it) {
        fout << setprecision(20) << fixed << (*it).x << " " << (*it).y << '\n';
    }
}