Cod sursa(job #1307220)

Utilizator gabrieligabrieli gabrieli Data 1 ianuarie 2015 17:59:40
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <cmath>
#include <algorithm>
#include <fstream>
#include <tuple>
#include <vector>
#include <iomanip>
using namespace std;

typedef pair<long double, long double> point_t;

inline
long double cosinus(const point_t& o, const point_t& p) {
    return (p.first - o.first) /
            sqrt((p.second - o.second)*(p.second - o.second) + 
                 (p.first - o.first)*(p.first - o.first));
}

inline
bool isCCW(const point_t& a, const point_t& b, const point_t& c) {
    return  (b.first - a.first)*(c.second - a.second) -
            (b.second - a.second)*(c.first - a.first) >= 0;
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    
    int n; fin >> n;
    
    vector<point_t> points;
    for (long double x, y; fin >> x >> y;) points.push_back({x, y});
    
    // choose "lowest-leftmost" point as the origin
    
    for (auto& p : points)
        if (p.second < points[0].second ||
                (p.second == points[0].second && p.first < points[0].first))
            swap(points[0], p);
    
    {   // sorting is done using the cosine of the points to the origin
        point_t origin = points[0];
        sort(points.begin() + 1, points.end(),
            [origin] (const point_t& a, const point_t& b) {
                return cosinus(origin, a) >= cosinus(origin, b);
            });
    }
    
    vector<point_t> hull;    
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    
    for (int i = 2; i < n; ++i) {
        while (hull.size() > 2 && !isCCW(hull[hull.size() - 2], hull.back(), points[i]))
            hull.pop_back();
        hull.push_back(points[i]);
    }
    
    while (hull.size() > 3 && !isCCW(hull[hull.size() - 2], hull.back(), points[0]))
        hull.pop_back();
    
    fout << hull.size() << '\n';
    for (auto p : hull)
        fout << setprecision(12) << p.first << ' ' << p.second << '\n';
    
    return 0;
}