Cod sursa(job #3252920)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 31 octombrie 2024 15:08:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Point
{
    T x,y;
    Point(const T &_x = 0, const T &_y = 0) : x(_x), y(_y) {}
};

template<typename T>
T compare(const Point<T> &a, const Point<T> &b)
{
    return (a.x - b.x) + (a.x - b.x == 0? a.y-b.y : 0);
}

#define define_point_comparator(op)\
template<typename T>\
bool operator op (Point<T> a, const Point<T> &b)\
{\
    return compare(a,b) op 0;\
}

#define define_point_operation(op)\
template<typename T>\
Point<T> operator op (Point<T> a, const Point<T> &b)\
{\
    a.x = a.x op b.x;\
    a.y = a.y op b.y;\
    return a;\
}

define_point_comparator(<)
define_point_comparator(>)
define_point_comparator(==)
define_point_comparator(!=)
define_point_comparator(<=)
define_point_comparator(>=)

define_point_operation(+)
define_point_operation(-)

template<typename T>
T signed_area(const Point<T> &a, const Point<T> &b, const Point<T> &c)
{
    return (a.x*b.y - a.x*c.y + b.x*c.y - b.x*a.y + c.x*a.y - c.x*b.y)/2;
}

template<typename T>
T area(const Point<T> &a, const Point<T> &b, const Point<T> &c)
{
    return abs(signed_area(a,b,c));
}

typedef Point<long double> point;

point v[120000];

int main()
{
    ifstream fin ("infasuratoare.in");
    ofstream fout ("infasuratoare.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n; fin>>n;
    int maxi = 0;
    point miny = 0;
    for(int i=0; i<n; ++i)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].x < v[maxi].x || (v[i].x == v[maxi].x && v[i].y < v[maxi].y))
            maxi = i;
    }
    swap(v[maxi], v[0]);
    sort(v+1, v+n, [&v](const point &a, const point &b){
                       return signed_area(*v,a,b) > 0 ||
                              signed_area(*v,a,b) == 0 && a.x <= b.x;
                   });
    deque<point> q;
    q.push_back(v[0]);
    for(int i=1; i<n; ++i)
    {
//        cout<<"i = "<<i<<"\n";
//        for(auto &i:q)
//        {
//            cout<<i.x<<' '<<i.y<<'\n';
//        }
//        cout<<"\n\n";
        while(q.size() > 1 && signed_area(*(q.end()-2), q.back(), v[i]) <= 0)
            q.pop_back();
        q.push_back(v[i]);
    }
    /*if(signed_area(*(q.end()-2), q.back(), v[0]) <= 0) q.pop_back();
    miny = *min_element(q.begin(), q.end(), [](const point &a, const point &b){return a.y < b.y || a.y == b.y && a.x < b.x;});
    while(q.front() != miny)
    {
        q.push_back(q.front());
        q.pop_front();
    }*/
    fout<<q.size()<<'\n';
    for(auto &i:q)
        fout<<fixed<<setprecision(10)<<i.x<<' '<<i.y<<'\n';
    return 0;
}