Cod sursa(job #1166400)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 3 aprilie 2014 15:56:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int inf = 0x3f3f3f3f;

typedef pair<double, double> POINT;

int N;
double x_min = inf, y_min = inf;
vector<pair<double, double> > P, ST;

inline int product(const POINT &A, const POINT &B, const POINT &C)
{
    double prod = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
    if (prod > 0)
        return 1;
    else if (prod == 0)
        return 0;
    return -1;
}

bool compare(const POINT &A, const POINT &B) { return (product(P[0], A, B) < 0); }

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

    int i, pos = -1, val;
    double x, y;
	scanf("%d", &N);

	for (i = 0; i < N; ++i)
    {
        scanf("%lf %lf", &x, &y);
        P.push_back(make_pair(x, y));

        if (y_min > y || (y_min == y && x_min > x))
        {
            x_min = x, y_min = y;
            pos = i;
        }
    }
    swap(P[0], P[pos]);
    sort(P.begin() + 1, P.end(), compare);

    ST.push_back(P[0]), ST.push_back(P[1]);

    for (i = 2; i < N; ++i)
    {
        val = product(ST[ST.size() - 2], ST[ST.size() - 1], P[i]);
        if (val == 0)
        {
            ST.pop_back();
            ST.push_back(P[i]);
        }
        else if (val < 0)
            ST.push_back(P[i]);
        else
        {
            while(val >= 0 && ST.size() > 2)
            {
                ST.pop_back();
                val = product(ST[ST.size() - 2], ST[ST.size() - 1], P[i]);
            }
            ST.push_back(P[i]);
        }
    }

    printf("%d\n", ST.size());
    for (i = 0; i < (int)ST.size(); ++i)
        printf("%lf %lf\n", ST[i].first, ST[i].second);

	fclose(stdout);
    return 0;
}