Cod sursa(job #1997315)

Utilizator cojocarugabiReality cojocarugabi Data 3 iulie 2017 21:43:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
/// a.cpp
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < decltype(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < pll >
# define pb push_back
# define pdd pair < db , db >
# define all(s) s.begin(),s.end()
# define CF
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n;
    static pdd s[125005];
    IOS;
    fi>>n;
    for (int i = 1;i <= n;++i)
        fi>>s[i].x>>s[i].y;
    auto Area = [&](db dX0, db dY0, db dX1, db dY1, db dX2, db dY2)
    {
        return ((dX1 - dX0)*(dY2 - dY0) - (dX2 - dX0)*(dY1 - dY0));
    };
    int mn = min_element(s + 1,s + 1 + n) - s;
    swap(s[1],s[mn]);
    sort(s + 2,s + 1 + n,[&](pdd a,pdd b)
         {
             return Area(s[1].x,s[1].y,a.x,a.y,b.x,b.y) >= 0;
         });
    static int p[1 << 18];
    int sz = 0;
    p[sz = 1] = 1;
    for (int i = 2;i <= n;++i)
    {
        while (sz >= 2 && Area(s[p[sz - 1]].x,s[p[sz - 1]].y,s[p[sz]].x,s[p[sz]].y,s[i].x,s[i].y) < 0)
            --sz;
        p[++sz] = i;
    }
    fo << sz << '\n';
    for (int i = 1;i <= sz;++i)
        fo << s[p[i]].x << ' ' << s[p[i]].y << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}