Cod sursa(job #88819)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 octombrie 2007 11:29:08
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 333
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 666000666
#define baga(t) x.pb(mp(P[t].f,t))

vector<pair<double,double> > P;
vector<pair<double,int> > x;
int N, K, A[NMAX][NMAX];
double Dd[NMAX], Du[NMAX], Area = INF;

void read()
{
        int i, x, y;
        freopen("popandai.in", "r", stdin);
        scanf("%d%d", &N, &K);
        for (i = 0; i < N; i++) scanf("%d%d", &x, &y), P.pb(mp((double)x,(double)y));
}

int sgn(int a, int b, int c)
{
        double x1 = P[a].f, x2 = P[b].f, x3 = P[c].f;
        double y1 = P[a].s, y2 = P[b].s, y3 = P[c].s;
        double sg = x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3;
        return (sg>0);
}

double area(int a, int b, int c)
{
        double x1 = P[a].f, x2 = P[b].f, x3 = P[c].f;
        double y1 = P[a].s, y2 = P[b].s, y3 = P[c].s;
        double s = x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3;
        return (abs(s)*0.5);
}

void solve()
{
        int i, j, k, s, np, n;
        int ii, jj, kk, sg;
        double a, pi = acos(0), t;

        sort(P.begin(), P.end());
        P.pb(mp(-1,-1));
        for (i = 1; i < N; i++)
        {
                for (j = 0; j < i; j++)
                {
                    P[N].f = (P[i].f+P[j].f)/2.0;
                    sg = sgn(N,i,j);
                    for (k = 0; k < N; k++)
                        if (sgn(k,i,j)==sg&&P[j].f<P[k].f&&P[i].f>P[k].f)
                           A[i][j]++;
                }
                for (j = 0; j < N; j++) A[j][i] = A[i][j];
        }

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                for (k = 0; k < N; k++) Dd[k] = Du[k] = INF;
                for (k = 0; k < N; k++)
                if (i!=k&&j!=k)
                {
                    x.clear();
                    baga(i); baga(j); baga(k);
                    sort(x.begin(), x.end());
                    ii = x[0].s; jj = x[2].s; kk = x[1].s;
                    if (sgn(kk,ii,jj)) {
                       np = A[ii][kk]+A[kk][jj]-A[ii][jj];
                       if (np<0) while(1);
                       a = area(i,j,k);
                       if ((a-Du[np])<eps) Du[np] = a; }
                    else {
                         np = A[ii][jj]-A[ii][kk]-A[jj][kk]-1;
                         if ( (P[kk].f >= P[jj].f) || (P[kk].f <= P[ii].f) ) np++;
                         if (np<0) while(1);
                         a = area(i,j,k);
                         if ((a-Dd[np])<eps) Dd[np] = a; }
                }
                for (k = 0; k <= K; k++)
                    if (Dd[k]+Du[K-k]<INF)
                       if ( (Dd[k]+Du[K-k]-Area)<eps ) Area = Dd[k]+Du[K-k];
            }
}

void write()
{
        freopen("popandai.out", "w", stdout);
        printf("%lf\n", Area);
}

int main()
{
        read();
        solve();
        write();
        return 0;
}