Cod sursa(job #2062650)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 10 noiembrie 2017 18:01:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define ld long double
#define pld pair<ld, ld>
#define x first
#define y second
#define pii pair<int,int>
const int Nmax = 120000 + 5;
pld p[Nmax], ans[Nmax];
stack<pii>S;
int m, n;
ld det = 0;
pld a, b, c;
bool cmp(pld p1, pld p2)
{
    if(p1.y == p2.y)
        return p1.x < p2.x;
    return p1.y < p2.y;
}
void inf(bool vr)
{
    S.push({2, 1});
    for(int i = 3; i <= n; ++i)
    {
        if(S.empty())
        {
            S.push({1, i});
            continue;
        }
        a = p[S.top().x];
        b = p[S.top().y];
        c = p[i];
        det = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
        if((!vr && det >= 0) || (vr && det < 0))
            S.push({S.top().y, i});
        else S.pop(), i--;
    }
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> p[i].x >> p[i].y;
    sort(p + 1, p + n + 1, cmp);
    inf(0);
    ans[1].x = p[1].x;
    ans[1].y = p[1].y;
    while(!S.empty())
    {
        ans[S.size() + 1].x = p[S.top().y].x;
        ans[S.size() + 1].y = p[S.top().y].y;
        ++m;
    }
    inf(1);
    while(!S.empty())
    {
        ++m;
        ans[m].x = p[S.top().y].x;
        ans[m].y = p[S.top().y].y;
    }
    --m;
    for(int i =1; i <= m; ++i)
        fout << p[i].x << " " << p[i].y << '\n';
    return 0;
}