Cod sursa(job #88850)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 octombrie 2007 15:52:04
Problema Popandai Scor 76
Compilator c Status done
Runda Arhiva de probleme Marime 5.41 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

#define NMAX 333
#define eps 1e-5

int X[NMAX], Y[NMAX], A[NMAX][NMAX];
int N, K, v[4][2], Sub[NMAX], Dea[NMAX], T[NMAX][NMAX], V[NMAX][NMAX];
long double U[NMAX], Area, Up[NMAX], Down[NMAX], INF;

double area(int a, int b, int c)
{
        double x1 = X[a], x2 = X[b], x3 = X[c];
        double y1 = Y[a], y2 = Y[b], y3 = Y[c];
        double s = x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3;
        if (s==0) s = -1;
        return (fabs(s)*0.5);
}

int add(int x, int y, int z)
{
        double arie;
        int i, num = 0;

        for (i = 0; i < Sub[z]; i++)
        {
            arie = area(x,y,z);
            if ((arie-area(x,y,T[z][i])-area(x,T[z][i],z)-area(T[z][i],y,z))==0) num++;
        }
        return num;
}

int add2(int x, int y, int z)
{
        double arie;
        int i, num = 0;

        for (i = 0; i < Dea[z]; i++)
        {
            arie = area(x,y,z);
            if ((arie-area(x,y,V[z][i])-area(x,V[z][i],z)-area(V[z][i],y,z))==0) num++;
        }
        return num;
}

int main()
{
        int val, i, j, k, p, np, x1, x2, x3, y1, y2, y3;
        int t, u, ii, jj, kk, z, rez, rez2;
        double sup;

        freopen("popandai.in","r",stdin);
        scanf("%d%d",&N,&K);

        for (i = 0; i < N; i++)
            scanf("%d %d", &X[i], &Y[i]);

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                if ( (X[i]>X[j])||(X[i]==X[j]&&Y[i]>Y[j]) )
                   val = X[i], X[i] = X[j], X[j] = val,
                   val = Y[i], Y[i] = Y[j], Y[j] = val;

        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                if (X[i]==X[j] && Y[i]>Y[j]) T[i][ Sub[i]++ ] = j;
                if (X[i]==X[j] && Y[i]<Y[j]) V[i][ Dea[i]++ ] = j;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                for (k = 0; k < N; k++)
                {
                       x1 = X[k]; x2 = X[i]; x3 = X[j];
                       y1 = Y[k]; y2 = Y[i]; y3 = Y[j];
                       rez=(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-x1*y3);
                       if (rez < eps)
                          if (X[k]>X[i]&&X[k]<X[j]) A[i][j]++;
                }

        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                if (!A[i][j]) A[i][j] = A[j][i];

       INF = 300000; INF *= (double)INF; INF += 666;
       Area = INF;
       for (i = 0; i < N; i++)
           for (j = i+1; j < N; j++)
           {
               for (k = 0; k < N; k++) Down[k] = Up[k] = INF;
               for (k = 0; k < N; k++)
                   if (i!=k&&j!=k)
                   {
                       v[0][0] = X[i]; v[1][0] = X[j]; v[2][0] = X[k];
                       v[0][1] = i; v[1][1] = j; v[2][1] = k;

                       for (t = 0; t < 3; t++)
                           for (u = t+1; u < 3; u++)
                               if (v[t][0]>v[u][0])
                                  for (z = 0; z < 2; z++)
                                      val = v[t][z], v[t][z] = v[u][z], v[u][z] = val;

                       ii = v[0][1]; jj = v[2][1]; kk = v[1][1];

                       x1 = X[k]; x2 = X[i]; x3 = X[j];
                       y1 = Y[k]; y2 = Y[i]; y3 = Y[j];
                       rez2=(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-x1*y3);
                       
                       x1 = X[kk]; x2 = X[ii]; x3 = X[jj];
                       y1 = Y[kk]; y2 = Y[ii]; y3 = Y[jj];
                       rez=(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-x1*y3);

                       if (rez2 > eps)
                       {
                           if (rez > eps) { np = A[ii][kk]+A[jj][kk]-A[ii][jj];
                                            np += add(ii, jj, kk);
                                            sup = area(i,j,k);
                                            if (sup-Up[np]<eps) Up[np] = sup; }
                           else { np = A[ii][jj]-A[ii][kk]-A[jj][kk]-1;
                                  np += add2(ii, jj, kk);
                                  if (X[kk]<=X[ii]||X[kk]>=X[jj]) np++;
                                  else np-=Sub[kk];
                                  sup = area(i,j,k);
                                  if (sup-Up[np]<eps) Up[np] = sup; }
                       }
                       else
                       {
                            if (rez > eps) { np = A[ii][kk]+A[jj][kk]-A[ii][jj];
                                             np += add(ii, jj, kk);
                                            sup = area(i,j,k);
                                            if (sup-Down[np]<eps) Down[np] = sup; }
                           else { np = A[ii][jj]-A[ii][kk]-A[jj][kk]-1;
                                  np += add2(ii, jj, kk);
                                  if (X[kk]<=X[ii]||X[kk]>=X[jj]) np++;
                                  else np-=Sub[kk];
                                  sup = area(i,j,k);
                                  if (sup-Down[np]<eps) Down[np] = sup; }
                       }
                   }
               for (k = 0; k <= K; k++)
               {
                   if ((Up[k]+Down[K-k])<INF)
                      if ( (Up[k]+Down[K-k]-Area) < eps ) Area = Up[k]+Down[K-k];
               }
            }

       freopen("popandai.out", "w", stdout);
       printf("%llf\n", Area);
            
       return 0;

}