Cod sursa(job #2454893)

Utilizator silviu982001Borsan Silviu silviu982001 Data 10 septembrie 2019 09:59:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

struct Point
{
    double x, y;
};

int n;
vector<Point> v, sol;

bool operator<(const Point& p1, const Point& p2)
{
    if (p1.y == p2.y)
        return p1.x > p2.x;
    
    return p1.y > p2.y;
}

long double determinant(const Point& p1, const Point& p2, const Point& p3)
{
    return p1.x * p2.y + p2.x * p3.y + p1.y * p3.x - p2.y * p3.x - p1.x * p3.y - p1.y * p2.x;
}

bool cmp(const Point& p1, const Point& p2)
{
    return determinant(v[0], p1, p2) < 0;
}

int main()
{
    ifstream fin("infasuratoare.in");
    fin >> n;
    
    for (int i = 0; i < n; ++i)
    {
        Point p;
        fin >> p.x >> p.y;
        v.push_back(p);
    }
    
    for (int i = 1; i < n; ++i)
        if (v[0] < v[i])
            swap(v[0], v[i]);
    
    sort(v.begin()+1, v.end(), cmp);
    
    sol.push_back(v[0]);
    
    for (int i = 1; i < n; ++i)
    {
        while (sol.size() > 1 && determinant(sol[sol.size() - 2], sol[sol.size() - 1], v[i]) > 0)
            sol.pop_back();
        
        sol.push_back(v[i]);
    }
    
    ofstream fout("infasuratoare.out");
    fout << sol.size() << '\n';
    for (Point p : sol)
        fout << setprecision(9) << fixed << p.x << ' ' << p.y << '\n';
    fout.close();
    
    return 0;
}