Cod sursa(job #2267393)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 23 octombrie 2018 16:39:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.12 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>;
using pdd = pair<double, double>;
#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>
void grahamScan(vector<pair<T,T>> v, vector<pair<T,T>>& ans) {
    ans.clear();

    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));
    
    ans.pb(v[0]);
    ans.pb(v[1]);
 
    for (int i = 2; i < (int)v.size(); ++i) {
        while (ans.size() >= 2) {
            pair<T,T> t1 = ans[ans.size() - 1];
            pair<T,T> t2 = ans[ans.size() - 2];
 
            T orient = getOrientation(t2, t1, v[i]);
            if (abs(orient) < EPS || orient < 0) {
                ans.pop_back();
            }
            else {
                break;
            }
        }
        ans.push_back(v[i]);
    }
}
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    in >> N;
    vector<pdd> v(N);
    for (auto& p : v) {
        in >> p.first >> p.second;
    }
 
    vector<pdd> ans;
    grahamScan(v, ans);
 
    out << ans.size() << '\n';
    out << fixed << setprecision(14);
    for (auto p : ans) {
        out << p.first << ' ' << p.second << '\n';
    }
    
    return 0;
}