Cod sursa(job #67744)

Utilizator floringh06Florin Ghesu floringh06 Data 25 iunie 2007 13:52:18
Problema Gradina Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 2.76 kb
using namespace std;

#define MAX_N 255
#define LIM 1<<16

#include <stdio.h>
#include <fstream>
#include <stdlib.h>

FILE *fin=fopen("gradina.in","r"),
     *fout=fopen("gradina.out","w");
         
typedef struct 
 {
  int x;
  int y;
 } point;
 
point p[MAX_N];
point p1[MAX_N]; //poligonul lui Ion
point p2[MAX_N]; //poligonul lui Vasile
int stat[MAX_N];
char sol[MAX_N];
int n,n1,n2;
double minn=10000000;

void citire (void)
{
  int i;
  fscanf(fin,"%d",&n);
  for (i=1; i<=n; i++)
   fscanf(fin,"%d %d",&p[i].x,&p[i].y);
}   

int testconvexity()
{
  int i,j,semn=0,a,b,c;
  for (i=1; i<=n1; i++)
   {       
     a=p1[i-1].y-p1[i].y;
     b=p1[i].x-p1[i-1].x;
     c=p1[i-1].x*p1[i].y-p1[i].x*p1[i-1].y;
     semn=(a*p1[3].x+b*p1[3].y+c);
     for (j=1; j<=n1; j++)
      if ((a*p1[j].x+b*p1[j].y+c)*semn<0) return 0; 
   }
  for (i=1; i<=n2; i++)
   {       
     a=p2[i-1].y-p2[i].y;
     b=p2[i].x-p2[i-1].x;
     c=p2[i-1].x*p2[i].y-p2[i].x*p2[i-1].y;
     semn=(a*p2[3].x+b*p2[3].y+c);
     for (j=1; j<=n2; j++)
      if ((a*p2[j].x+b*p2[j].y+c)*semn<0) return 0; 
   }         
  return 1;
}   

int testintersection()
{
  int i,j,semn=0,a,b,c;
  for (i=1; i<=n1; i++)
   {       
     a=p1[i-1].y-p1[i].y;
     b=p1[i].x-p1[i-1].x;
     c=p1[i-1].x*p1[i].y-p1[i].x*p1[i-1].y;
     semn=(a*p2[3].x+b*p2[3].y+c);
     for (j=1; j<=n2; j++)
      if ((a*p2[j].x+b*p2[j].y+c)*semn<0) return 0; 
   }
  return 1;
}   

double arie()
{ 
  int i;
  double arie1,arie2,comp;
  for (i=1; i<=n1-1; i++)
   arie1+=p1[i].x*p1[i+1].y-p1[i+1].x-p1[i].y;
  arie1/=2; 
  for (i=1; i<=n2-1; i++)
   arie2+=p2[i].x*p2[i+1].y-p2[i+1].x-p2[i].y;
  arie2/=2;
  if (arie1>arie2) comp=double(arie1-arie2);
      else comp=double (arie2-arie1); 
  return comp;
}      
  

void solve (void)
{
 int d,d1,i,t1,t2,semn,j1,j2;
 double comp;
 memset(stat,0,sizeof(stat));
 for (d=0; d<=LIM; d++)
 {
  for (d1=1; d1<=n; d1++)         
   { 
    semn=rand() % n;
    if (stat[semn]==d%2)
     if (stat[semn]==1) stat[semn]=0; 
      else stat[semn]=1;
   }
  t1=testconvexity();
  t2=testintersection();
  j1=0; j2=0;       
  for (i=1; i<=n; i++)
      if (stat[i]==1) p1[++j1]=p[i];
       else p2[++j2]=p[i];
  n1=j1; n2=j2; 
  if (n1<3 || n2<3) continue;    
  t1=testconvexity();
  t2=testintersection();
  if (t1==1 && t2==1)
  {
   comp=arie();
   if (comp<minn)
    {
       minn=double(comp);
       for (i=1; i<=n; i++)
        if (stat[i]==1) sol[i]='I'; else sol[i]='V';
    }
   }
 } 
  fprintf(fout,"%.1f\n",minn);
  for (i=1; i<=n; i++)
   fprintf(fout,"%c",sol[i]);      
}          

int main()
{
   citire();
    
   solve();
   
   fclose(fin);
   fclose(fout);
   
   return 0;
}