Cod sursa(job #2642515)

Utilizator lior5654Lior Yehezkely lior5654 Data 15 august 2020 19:08:46
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 8.44 kb
#include <bits/stdc++.h>
#include <type_traits>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including 

using namespace std;


/*using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/

typedef long long int ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpi> vvpi;
typedef vector<vpl> vvpl;
typedef set<int> si;
typedef multiset<int> msi;
typedef set<ll> sl;
typedef multiset<ll> msl;

#define clrcin cin.ignore(numeric_limits<streamsize>::max(),'\n');
#define GOGOGO ios::sync_with_stdio(false); cin.tie(nullptr);
#define BYEBYE return 0;

#define all(cn) (cn).begin(), (cn).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define repk(i, k, n) for(int i = k; i < n; ++i)

#define mp make_pair
#define pb push_back
#define fi first
#define se second

#define popcnt __builtin_popcount
#define gcd std::__detail::__gcd
#define lcm std::__detail::__lcm

const int INFI = 1e9 + 5;
const ll INFL = 4e18 + 5;

template<class T> void aread(T* arr, int ___n)
{
    rep(i, ___n)
    {
        cin >> arr[i];
    }
}

/************************************************* BEGIN GEOMETRY TEMPLATE *************************************************/
/************************************************* BEGIN GEOMETRY TEMPLATE *************************************************/
/************************************************* BEGIN GEOMETRY TEMPLATE *************************************************/

// helpful: https://cp-algorithms.com/geometry/basic-geometry.html#toc-tgt-7

/*
Helpful Notes:

vector can be represented with pt.

** dot product **
0. dot(a, b) = a.x * b.x + a.y * b.y
1. a*b = b*a
2. (crd*a)*b = crd*(a*b)
3. (a+b)*c = a*c + b*c
4. norm(v) = v*v
5. abs(v) = sqrt(norm(v)) // length of the vector

** cross product **
0. cross(a, b) = a.x * b.y - a.y * b.x
1. cross(a, b) = -cross(b, a)
2. cross(a, b) == 0 <=> a & b are collinear
3. 
*/


typedef long double ld;

#define EPS ((ld)1e-9)

template<class crd> ll sgn(const crd& x) {
  return x > ((crd)EPS) ? 1 : x < ((crd)-EPS) ? -1 : 0;
}
template<class crd> struct pt
{
    crd x; crd y;
    pt& operator=(const pt& other)
    {
        x=other.x; y=other.y;
        return *this;
    }
    pt& operator+=(const pt& other)
    {
        x+=other.x; y+=other.y;
        return *this;
    }
    pt& operator-=(const pt& other)
    {
        x-=other.x; y-=other.y;
        return *this;
    }
    pt& operator*=(const crd& t)
    {
        x*=t; y*=t;
        return *this;
    }
    pt& operator/=(const crd& t)
    {
        assert(t!=0);
        x/=t; y/=t;
        return *this;
    }
    pt operator+(const pt& other) const
    {
        return pt<crd>(*this) += other;
    }
    pt operator-(const pt& other) const
    {
        return pt<crd>(*this) -= other;
    }
    pt operator*(const crd& t) const
    {
        return pt<crd>(*this) *= t;
    }

    pt operator/(const crd& t) const
    {
        return pt<crd>(*this) /= t;
    }
    operator pt<ld>() const
    {
        pt<ld> newpt;
        newpt.x = this->x; newpt.y = this->y;
        return newpt;
    }
};

template<class crd> pt<crd> operator*(const crd& t, const pt<crd>& pt)
{
    return pt * t;
}

template<class crd> crd dot(const pt<crd>& l, const pt<crd>& r) // dot(l, r) = dot(r, l)
{
    return l.x * r.x + l.y * r.y;
}
template<class crd> crd norm(const pt<crd>& a)
{
    return dot(a, a);
}
template<class crd> ld abs(const pt<crd>& a)
{
    return sqrtl(norm(a));
}
template<class crd> crd cross(const pt<crd>& l, const pt<crd>& r) // cross(l, r) = -cross(r, l)
{
    return l.x * r.y - l.y * r.x;
}

template<class crd> bool upper(const pt<crd>& a) {
  return ((a.y > 0) || (!a.y && a.x > 0));
}

template<class crd> bool operator<(const pt<crd> &a, const pt<crd> &b) {
    if(upper(a) != upper(b)) return upper(a);
    return cross(a, b) > 0;
}

bool operator<(const pt<ld> &a, const pt<ld> &b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x) - EPS;
}

/*
@ brief: find intersection of two lines (or their continuation)
NOTE: will crash due to division by 0 if lines are collinear
*/
pt<ld> intersection(const pt<ld>& a1, const pt<ld>& a2, const pt<ld>& b1, const pt<ld>& b2)
{
    return a1 + ((a2 - a1) * cross(b1 - a1, b2 - b1) / cross(a2 - a1, b2 - b1));
}

template<class crd> bool intersection1d(crd l1, crd r1, crd l2, crd r2)
{
    // note to self: this takes cases of the right and left points of the segment being flipped
    if (l1 > r1)
    {
        r1 += l1;
        l1 = r1 - l1;
        r1 -= l1;
    }
    if (l2 > r2)
    {
        r2 += l2;
        l2 = r2 - l2;
        r2 -= l2;
    }
    return max(l1, l2) <= min(r1, r2) + ((crd)EPS);
} 

/*
@ brief: whether or not two given line segments (a1-a2, b1-b2) intersect
*/
template<class crd> bool segseg(const pt<crd>& a1, const pt<crd>& a2, const pt<crd>& b1, const pt<crd>& b2) {
    return intersection1d(a1.y, a2.y, b1.y, b2.y) && intersection1d(a1.x, a2.x, b1.x, b2.x) && 
        sgn(cross(a1 - b1, b2 - b1)) * sgn(cross(a2 - b1, b2 - b1)) <= 0 &&
        sgn(cross(b1 - a1, a2 - a1)) * sgn(cross(b2 - a1, a2 - a1)) <= 0;
}

/*
@ brief: area of polygon, points ordered by edge order
*/
template<class crd> ld polyarea(const vector<pt<crd>>& points)
{
    int sz = points.size();
    ld res = 0;
    for(int i = 0; i < sz; ++i)
    {
        res += (ld)cross(points[i], points[(i==sz-1)?0:i+1]);
    }
    return abs(res / 2.0);
}
/*
@ brief: evaluate y value for a given x on a line
*/
ld evaluate_line(const pt<ld>& a, const pt<ld>& b, ld x)
{                                      
    if(abs(a.x - b.x) < EPS)
    {
        return a.y;
    }
    return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}

template<class crd> bool cw(const pt<crd>& o, const pt<crd>& a, const pt<crd>& b)
{
    return cross(b-o, a-o) > 0;
}
template<class crd> bool ccw(const pt<crd>& o, const pt<crd>& a, const pt<crd>& b)
{
    return cross(b-o, a-o) < 0;
}

template<class crd> void get_hull_side(const vector<pt<crd>>& gpts, vector<pt<crd>>& hull_side, bool side) // side=true => uppper, otherwise lower
{
    if(gpts.size() <= 1)
    {
        return;
    }
    hull_side.push_back(gpts[0]);
    int sz = gpts.size();
    for(int i = 1; i < sz; ++i)
    {
        if(i == sz - 1 || ((side && cw(gpts[0], gpts[i], gpts[sz-1])) || (!side && ccw(gpts[0], gpts[i], gpts[sz-1]))))
        {
            while((int)hull_side.size() >= 2 && ((side && !cw(hull_side[(int)hull_side.size()-2], hull_side[(int)hull_side.size()-1], gpts[i])) ||
                                                 (!side && !ccw(hull_side[(int)hull_side.size()-2], hull_side[(int)hull_side.size()-1], gpts[i]))))
            {
                hull_side.pop_back();
            }
            hull_side.push_back(gpts[i]);
        }
    }
} 
/*
@ brief: get convex hull of points, output sorted by trigonometric order
*/
template<class crd> vector<pt<crd>> convex_hull(vector<pt<crd>> pts) // replace to reference if you need the sorted order later
{
    if(pts.size() <= 1)
    {
        return vector<pt<crd>>();
    }
    vector<pt<crd>> hull;
    vector<pt<crd>> upper;
    vector<pt<crd>> lower;
    sort(all(pts), [](const pt<crd>& a, const pt<crd>& b){return a.x < (b.x - ((crd)EPS)) || ((a.x - b.x) < ((crd)EPS) && a.y < (b.y - ((crd)EPS)));}); // sorting for graham's scan
    get_hull_side(pts, upper, true);
    get_hull_side(pts, lower, false);
    int usz = upper.size();
    int lsz = lower.size();
    //cout << upper.size() << endl;
    for(int i = usz - 1; i >= 0; --i)
    {
        hull.pb(upper[i]);
    }
    for(int i = 1; i < lsz - 1; ++i)
    {
        hull.pb(lower[i]);
    }
    return hull;


}


int main()
{
    freopen("infasuratoare.in", "r", stdin); 
    freopen("infasuratoare.in", "w", stdout);
    cout << fixed << setprecision(6);
    int n; cin >> n;
    vector<pt<ld>> in(n);
    rep(i, n)
    {
        cin >> in[i].x >> in[i].y;
    }
    vector<pt<ld>> ch = convex_hull(in);
    cout << ch.size() << endl;
    for(auto e : ch)
    {
        cout << e.x << " " << e.y << endl;
    }
    return 0;
}