Cod sursa(job #2046197)

Utilizator LucaSeriSeritan Luca LucaSeri Data 23 octombrie 2017 16:06:22
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct p{
    long double x, y;
}v[120010];

long double det(long double x1, long double y1, long double x2, long double y2, long double x3, long double y3){
    return x1*y2 + x2*y3 + x3*y1 - y2*x3 - x2*y1 - x1*y3;
}

class cmp{
public:
    bool operator()(const p &a, const p &b){
        if(det(v[0].x, v[0].y, a.x, a.y, b.x, b.y) > 0) return true;
        if(det(v[0].x, v[0].y, a.x, a.y, b.x, b.y) < 0) return false;
        return a.x < b.x;
    }
};

vector<p> sol;

int main(){
    int n;
    f >> n;
    f >> v[0].x >> v[0].y;
    for(int i = 1; i < n; ++i){
        f >> v[i].x >> v[i].y;
        if(v[i].x < v[0].x || (v[i].x == v[0].x && v[i].y < v[0].y)){
            swap(v[i], v[i]);
        }
    }
    sort(v + 1, v + n, cmp());
    sol.push_back(v[0]);
    for(int i = 1; i < n; ++i){
        bool am_scos = true;
        while(sol.size() >= 2 && am_scos){
            am_scos = false;
            p a = sol.back();
            sol.pop_back();
            if(det(sol.back().x, sol.back().y, a.x, a.y, v[i].x, v[i].y) <= 0){
                am_scos = true;
            }
            else sol.push_back(a);
        }
        sol.push_back(v[i]);
    }
    g << sol.size() << '\n';
    for(int i = 0; i < sol.size(); ++i){
        g << setprecision(12) << fixed << sol[i].x << ' ' << sol[i].y << '\n';
    }
    return 0;
}