Cod sursa(job #88795)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 3 octombrie 2007 23:03:44
Problema Popandai Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 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

vector<pair<int,int> > P;
vector<pair<double,int> > V;
int N, K, A[NMAX][NMAX];
double D[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(x,y));
}

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

double area(int a, int b, int c)
{
        int x1 = P[a].f, x2 = P[b].f, x3 = P[c].f;
        int y1 = P[a].s, y2 = P[b].s, y3 = P[c].s;
        int 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;
        double a;

        sort(P.begin(), P.end());
        P.pb(mp(-1,-1));
        for (i = N-1; i >= 0; i--)
        {
                V.clear();
                for (j = i+1; j < N; j++)
                    V.pb(mp(atan2((double)(P[i].s-P[j].s), (double)(P[i].f-P[j].f)), j));
                sort(V.begin(), V.end());
                n = V.size();
                j = V[0].s;
                P[N].f = P[i].f+1;
                s = sgn(N,i,j);
                for (k = 0; k < N; k++)
                    if (sgn(k,i,j)==s&&P[i].f<P[k].f&&P[j].f>P[k].f) A[i][j]++;
                for (k = 1; k < n; k++)
                {
                        j = V[k].s;
                        A[i][j] = A[i][j-1]+A[j-1][j];
                }
                for (k = 0; k < n; k++)
                {
                        j = V[k].s;
                        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++) D[k] = INF;
                for (k = j+1; k < N; k++)
                {
                    if (sgn(k,i,j)) np = A[i][k]+A[j][k]-A[i][j];
                    else np = A[i][j]-A[i][k]-A[j][k]-1;
                    a = area(i,j,k);
                    if ((a-D[np])<eps) D[np] = a;
                }
                for (k = 0; k <= K; k++)
                    if (D[k]+D[K-k]<INF)
                       if ( (D[k]+D[K-k]-Area)<eps ) Area = D[k]+D[K-k];
            }
}

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

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