Cod sursa(job #2267390)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 23 octombrie 2018 16:32:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.08 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>
void 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));
    
    vector<pair<T,T>> stk(v.size());
    stk[0] = v[0];
    stk[1] = v[1];
    int head = 1;
 
    for (int i = 2; i < (int)v.size(); ++i) {
        while (head >= 1) {
            pair<T,T> t1 = stk[head];
            pair<T,T> t2 = stk[head - 1];
 
            T orient = getOrientation(t2, t1, v[i]);
            if (abs(orient) < EPS || orient < 0) {
                --head;
            }
            else {
                break;
            }
        }
        stk[++head] = v[i];
    }
 
    out << head + 1 << '\n';
    out << fixed << setprecision(12);
    for (int i = 0; i <= head; ++i) {
        out << stk[i].first << ' ' << stk[i].second << '\n';
    }
}
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    in >> N;
    vector<pair<double,double>> v(N);
    for (auto& p : v) {
        in >> p.first >> p.second;
    }
 
    grahamScan(v); 
    
    return 0;
}