Cod sursa(job #1884783)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 19 februarie 2017 11:17:33
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;

int n;
pair<double, double> puncte[120005];
pair<double, double> solutie[120005];
pair<int, int> fir;

double determinant(pair<int, int> x, pair<int, int> y, pair<int, int> z)
{
    return (y.first - x.first) * (z.second - x.second) - (y.second - x.second) * (z.first - x.first);
}

bool compare(pair<int, int> x, pair<int, int> y)
{
    return (determinant(fir, x, y) > 0);
}

void citire()
{
    scanf("%d", &n);

    double tmp1, tmp2;

    for(int i = 0; i < n; i++)
    {
        scanf("%lf %lf", &tmp1, &tmp2);
        puncte[i] = make_pair(tmp1, tmp2);
    }

    int minx = 0, miny = 0;

    for(int i = 0; i < n; i++)
    {
        if(puncte[i].first < puncte[minx].first)
        {
            minx = i;
        }
    }

    for(int i = 0; i < n; i++)
    {
        if(puncte[i].first == puncte[minx].first && puncte[i].second < puncte[miny].second)
        {
            miny = i;
        }
    }

    swap(puncte[0], puncte[miny]);
    fir = puncte[0];
}

void solve()
{
    sort(puncte + 1, puncte + n, compare);

    solutie[0] = puncte[0];
    solutie[1] = puncte[1];

    int k = 2;

    for(int j = 2; j < n; j++, k++)
    {
        while(determinant(puncte[k - 2], puncte[k - 1], puncte[j]) < 0 && k > 0)
        {
            k--;
        }
        puncte[k] = puncte[j];
    }

    printf("%d\n", k);

    printf("%lf %lf\n", puncte[0].first, puncte[0].second);

    for(int i = 1; i < k; i++)
    {
        printf("%lf %lf\n", puncte[i].first, puncte[i].second);
    }
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    citire();
    solve();

    return 0;
}