Cod sursa(job #1946710)

Utilizator ZenusTudor Costin Razvan Zenus Data 30 martie 2017 12:53:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 120009;

#define point pair < double , double >

point p[nmax] , up[nmax] , low[nmax];
int n , i , upS , lowS;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

bool cmp1(point A , point B)
{
    return A < B;
}

bool cmp2(point A , point B)
{
    return A > B;
}

void readData()
{
    fin >> n;
    for (i = 1 ; i <= n ; ++i)
    fin >> p[i].first >> p[i].second;
}

void upperEnvelope()
{
    sort(p + 1 , p + n + 1 , cmp1);

    for (i = 1 ; i <= n ; ++i)
    {
        while (2 <= upS)
        {
            point A = up[upS - 1];
            point B = up[upS];
            point C = p[i];

            if ((A.second - B.second) * (A.first - C.first) <= (A.second - C.second) * (A.first - B.first))
            upS--;
            else break;
        }
        up[++upS] = p[i];
    }
}

void lowerEnvelope()
{
    sort(p + 1 , p + n + 1 , cmp2);

    for (i = 1 ; i <= n ; ++i)
    {
        while (2 <= lowS)
        {
            point A = low[lowS - 1];
            point B = low[lowS];
            point C = p[i];

            if ((A.second - B.second) * (A.first - C.first) <= (A.second - C.second) * (A.first - B.first))
            lowS--;
            else break;
        }
        low[++lowS] = p[i];
    }
}

int main()
{

readData();
upperEnvelope();
lowerEnvelope();

fout << upS + lowS - 2 << '\n';
for (i = upS ; i ; --i)
{
    fout << fixed << setprecision(10) << up[i].first << " ";
    fout << fixed << setprecision(10) << up[i].second << '\n';
}

for (i = lowS - 1 ; 2 <= i ; --i)
{
    fout << fixed << setprecision(10) << low[i].first << " ";
    fout << fixed << setprecision(10) << low[i].second << '\n';
}

return 0;
}