Cod sursa(job #67651)

Utilizator raula_sanChis Raoul raula_san Data 25 iunie 2007 13:02:13
Problema Gradina Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 3.02 kb
#include <cstdio>
#include <cmath>

#define MAX_N 256

int X[MAX_N], Y[MAX_N], C[MAX_N], A[MAX_N], B[MAX_N], SOL[MAX_N];
int N;

double dmin, A1, A2;

void READ();
void GEN();
void PRINT();

double Area(int, int, int);
double D(int, int, int, int);

int Intersect();

int InteriorA(int, int);
int InteriorB(int, int);

int main()
{
    dmin = 0x3f3f3f3f;
    
    READ();
    GEN();
    PRINT();
    
    return 0;
}

void READ()
{
     FILE *f = fopen("gradina.in", "rt");
     int i;
     
     for(fscanf(f, "%d", &N), i=1; i<=N; ++i)
                   fscanf(f, "%d %d", X+i, Y+i);
     
     fclose(f);
}

void GEN()
{
     long long unsigned i, limit, j;
     int k;
     
     limit = 1 << (N - 1);
     
     for(i=1; i<limit; ++i)
     {
           k = N;
           j = i;
           
           while(j)
           {
                   C[k--] = j & 1;
                   j >>= 1;
           }
           
           A[0] = B[0] = 0;

	   for(j=1; j<=N; ++j)
                    if(!C[j])
                             A[++A[0]] = j;
                    else
                        B[++B[0]] = j;
                    
	   if(A[0] >= 3 && B[0] >= 3)
	   {

	   A1 = A2 = 0;

	   for(j=2; j<A[0]; ++j)
		    A1 += Area(A[1], A[j], A[j+1]);
	   for(j=2; j<B[0]; ++j)
		    A2 += Area(B[1], B[j], B[j+1]);

	   A1 -= A2;

	   A1 *= A1 < 0 ? -1 : 1;
           
	   if(A1 < dmin && !Intersect())
	   {
		 dmin = A1;

		 for(j=1; j<=N; ++j)
			  SOL[j] = C[j];
	   }

	   }
     }
}

void PRINT()
{
     FILE *g = fopen("gradina.out", "wt");
     int i;
     
     fprintf(g, "%.1lf\n", dmin);
     
     for(i=1; i<=N; ++i)
              if(!SOL[i])
                         fprintf(g, "I");
              else
                  fprintf(g, "V");
     
     fclose(g);
}

double Area(int i, int j, int k)
{
       double a, b, c, p;
       
       a = D(X[i], Y[i], X[j], Y[j]);
       b = D(X[j], Y[j], X[k], Y[k]);
       c = D(X[i], Y[i], X[k], Y[k]);
       
       p = (a + b + c) / 2;
       
       return
             sqrt(p * (p-a) * (p-b) * (p-c));
}

double D(int xa, int ya, int xb, int yb)
{
       return
             sqrt( (xa-xb) * (xa-xb) + (ya-yb) * (ya-yb) );
}

int Intersect()
{
    int i;
    
    for(i=1; i<=A[0]; ++i)
             if(InteriorB(X[A[i]], Y[A[i]]))
				   return 1;

    for(i=1; i<=B[0]; ++i)
	     if(InteriorA(X[B[i]], Y[B[i]]))
				   return 1;

    return 0;
}

int InteriorA(int x, int y)
{
    double P1 = 0;
    
    X[N+1] = x;
    Y[N+1] = y;
    
    P1 += Area(A[1], A[A[0]], N+1);
    
    int i;
    
    for(i=2; i<A[0]; ++i)
             P1 += Area(N+1, i, i+1);
             
    return P1 == A1;
}

int InteriorB(int x, int y)
{
    double P2 = 0;
    
    X[N+1] = x;
    Y[N+1] = y;
    
    P2 += Area(B[1], B[B[0]], N+1);
    
    int i;
    
    for(i=2; i<B[0]; ++i)
             P2 += Area(N+1, i, i+1);
             
    return P2 == A2;
}