Cod sursa(job #2410144)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 19 aprilie 2019 19:39:42
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pld;

const string file = "infasuratoare";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 120005;

int n, vf;
pld v[nmax], first = {inf, inf}, s[nmax];

bool rightturn(pld a, pld b, pld c)
{
    ld sum = 0;
    sum += a.ff*b.ss;
    sum += b.ff*c.ss;
    sum += c.ff*a.ss;
    sum -= c.ff*b.ss;
    sum -= b.ff*a.ss;
    sum -= a.ff*c.ss;
    return sum < 0;
}

bool cmp(pld a, pld b)
{
    return (a.ss-first.ss)*(b.ff-first.ff) > (b.ss-first.ss)*(a.ff-first.ff);
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i].ff >> v[i].ss;
        first = min(first, v[i]);
    }
    for (int i = 1; i <= n; ++i)
        if(v[i] == first){
            for (int j = i; j < n; ++j)
                v[j] = v[j+1];
            --n;
            break;
        }
    sort(v+1, v+n+1, cmp);
    s[++vf] = first;
    s[++vf] = v[1];
    for (int i = 2; i <= n; ++i){
        while(vf >= 2 && !rightturn(s[vf-1], s[vf], v[i]))
            --vf;
        s[++vf] = v[i];
    }
    fout << vf << "\n";
    for (int i = vf; i >= 1; --i)
        fout << s[i].ff << " " << s[i].ss << "\n";
    return 0;
}