Cod sursa(job #3214624)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 14 martie 2024 11:35:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()


struct Point
{
    double x,y;
    bool operator <(const Point& b)const
    {
        if(y==b.y)
        {
            return x<b.x;
        }
        return y<b.y;
    }
};

double det(const Point& a,const Point& b,const Point& c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    int n;
    cin>>n;
    vector<Point>a(n);
    for(auto &c:a)
    {
        cin>>c.x>>c.y;
    }

    vector<Point>::iterator it=min_element(all(a));
    auto element=*it;
    a.erase(it);

    sort(all(a),[&](const Point& l,const Point& r){
        return det(element , l,r)>0;
    });

    vector<Point>d={element};

    for(auto &c:a)
    {
        while((int)d.size()>1 && det(d[d.size()-2] , d[d.size()-1] , c)<0)
        {
            d.pop_back();
        }
        d.push_back(c);
    }

    cout<<d.size()<<'\n';
    cout<<fixed<<setprecision(12);
    for(auto &c:d)
    {
        cout<<c.x<<' '<<c.y<<'\n';
    }
}