Cod sursa(job #2267365)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 23 octombrie 2018 16:09:36
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.26 kb
#include <bits/stdc++.h>
  
using namespace std;
  
#if 1
    #define pv(x) cout<<#x<<" = "<<(x)<<"; ";cout.flush()
    #define pn cout<<endl
#else
    #define pv(x)
    #define pn
#endif
  
// #if 1
#ifdef INFOARENA
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
#else
    #define in cin
    #define out cout
#endif
  
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld, ld>;
#define pb push_back
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862;
const long double EPS = 1e-8;
const int inf_int = 1e9 + 5;
const ll inf_ll = 1e18 + 5;
const int NMax = 2e2 + 5;
const int mod = 1e9 + 7;
const int dx[] = {-1,0,0,+1}, dy[] = {0,-1,+1,0};

template<typename T>
T distSquare(pair<T,T> a, pair<T,T> b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

template<typename T>
T getOrientation(pair<T,T> a, pair<T,T> b, pair<T,T> c) {
    T ans = a.first * b.second + b.first * c.second + c.first * a.second;
    ans -= c.first * b.second + b.first * a.second + a.first * c.second;
    return ans;
}

template<typename T>
double getQuadrant(pair<T,T> point) {
    if (point.first == 0 && point.second == 0) {
        return 0.0;
    }

    if (point.first > 0 && point.second == 0) {
        return 0.5;
    }

    if (point.first > 0 && point.second > 0) {
        return 1.0;
    }    

    if (point.first == 0 && point.second > 0) {
        return 1.5;
    }

    if (point.first < 0 && point.second > 0) {
        return 2.0;
    }

    if (point.first < 0 && point.second == 0) {
        return 2.5;
    }

    if (point.first < 0 && point.second < 0) {
        return 3.0;
    }

    if (point.first == 0 && point.second < 0) {
        return 3.5;
    }

    return 4.0;
}

template<typename T>
bool polarCompare(pair<T,T> source, pair<T,T> a, pair<T,T> b) {
    a.first -= source.first;
    a.second -= source.second;
    b.first -= source.first;
    b.second -= source.second;

    int q1 = getQuadrant(a), q2 = getQuadrant(b);
    if (q1 == q2) {
        T orient = getOrientation({0,0}, a, b);
        if (abs(orient) < EPS) {
            T distA = distSquare({0,0}, a);
            T distB = distSquare({0,0}, b);
            return distA < distB;
        }
        return ((orient > 0) ? true : false);
    }
    return q1 < q2;
}

template<typename T>
vector<pair<T,T>> grahamScan(vector<pair<T,T>> v) {
    pair<T,T> mn = {1e18, 1e18};
    for (auto p : v) {
        if (p.second < mn.second) {
            mn = p;
        }
        else if (p.second == mn.second && p.first < mn.first) {
            mn = p;
        }
    }

    struct helper {
        pair<T,T> origin;
        helper(pair<T,T> _origin) {
            origin = _origin;
        }

        bool operator () (pair<T,T> a, pair<T,T> b) {
            return polarCompare(origin, a, b);
        }
    };

    sort(v.begin(), v.end(), helper(mn));
    
    stack<pair<T,T>> stk;
    stk.push(v[0]);
    stk.push(v[1]);

    for (int i = 2; i < (int)v.size(); ++i) {
        while (stk.size() >= 2) {
            pair<T,T> t1 = stk.top(); stk.pop();
            pair<T,T> t2 = stk.top(); stk.pop();
            stk.push(t2);
            stk.push(t1);

            T orient = getOrientation(t2, t1, v[i]);
            if (abs(orient) < EPS || orient < 0) {
                stk.pop();
            }
            else {
                break;
            }
        }
        stk.push(v[i]);
    }

    vector<pair<T,T>> ans;
    while (stk.size()) {
        ans.pb(stk.top());
        stk.pop();
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    in >> N;
    vector<pld> v(N);
    for (auto& p : v) {
        in >> p.first >> p.second;
    }

    vector<pld> ans = grahamScan(v);

    out << ans.size() << '\n';
    out << fixed << setprecision(14);
    for (auto p : ans) {
        out << p.first << ' ' << p.second << '\n';
    }
    
    return 0;
}