Cod sursa(job #1171411)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 15 aprilie 2014 18:38:17
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <fstream>
#include <algorithm>
#include <utility>
#include <iomanip>

#define point pair<int,int>
#define x first
#define y second
#define maxn 301
#define inf 900000000

using namespace std;

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

point v[maxn];
int under[maxn][maxn],n,K;

double a1[maxn],a2[maxn],par1[maxn],par2[maxn],ans=inf;

int det (point a, point b, point c)
{
    return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}

double area (point a, point b, point c)
{
    double A = det (a,b,c);

    if (A < 0)
        return -A/2;
    return A/2;
}

int main()
{
    fin>>n>>K;

    for (int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
    }

    sort (v+1,v+n+1);

    for (int i=1; i<=n; ++i)
    {
        for (int j=i+1; j<=n; ++j)
        {
            for (int k=i+1; k<j; ++k)
            {
                if (det(v[i],v[j],v[k]) < 0)
                    ++under[i][j];
            }
        }
    }

    for (int i=1; i<=n; ++i)
    {
        for (int j=i+1; j<=n; ++j)
        {
            for (int k=0; k<=K; ++k)
            {
                a1[k] = inf;
                a2[k] = inf;
            }

            for (int k = 1; k<=n; ++k)
            {
                if (k == i || k == j)
                    continue;

                int ii = i, jj = j, kk = k;

                if (kk > jj)
                    swap (kk,jj);
                if (kk < ii)
                    swap (ii,kk);

                double a = area (v[i],v[j],v[k]);

                int in = under[ii][kk] + under[kk][jj] - under[ii][jj];
                if (in < 0)
                    in = -in - 1;

                if (det(v[i],v[j],v[k]) > 0)
                    a1[in] = min (a1[in],a);
                else a2[in] = min (a2[in],a);
            }

            par1[K] = a1[K];
            par2[K] = a2[K];

            for (int k=K-1; k>=0; --k)
            {
                par1[k] = min (a1[k],par1[k+1]);
                par2[k] = min (a2[k],par2[k+1]);
            }

            for (int k=0; k<=K; ++k)
                ans = min (ans,par1[k]+par2[K-k]);
        }
    }

    fout<<fixed<<setprecision(1)<<ans;
}