Cod sursa(job #1515840)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 2 noiembrie 2015 11:54:48
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.77 kb
#include <bits/stdc++.h>
#define eps 1e-12
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
const int nmax = 250;
struct punct {double x,y;} a[nmax];
int n,st_siz,dr_siz,ord_dr_siz,ord_st_siz;
long long difmin=INT_MAX,ar1,ar2;
int ras[nmax],parte[nmax];
punct P1,P2;
char fin[nmax],auxr[nmax];
punct st[nmax],dr[nmax],stiv1[nmax],stiv2[nmax],ord_st[nmax],ord_dr[nmax];

bool cmp (punct A , punct B)
{
    if (A.x!=B.x) return A.x<B.x;
    return A.y<B.y;
}

int cross_product (punct O,punct A ,punct B)
{
    A.x-=O.x;
    A.y-=O.y;
    B.x-=O.x;
    B.y-=O.y;
    return A.x*B.y-A.y*B.x;
}

void create_answer ()
{
    int i;
    int verif;
    verif=parte[1];
    for (i=1;i<=n;i++)
    {
        if (parte[i]==verif)
            auxr[i-1]='I';
        else
            auxr[i-1]='V';
    }

    auxr[n]=NULL;
}

long long arie (punct V[nmax],int V_siz)
{
    double sol=0;
    int h;
    for (h=1;h<V_siz;h++)
     sol+=V[h].x*V[h+1].y-V[h+1].x*V[h].y;

    sol+=V[V_siz].x*V[1].y-V[1].x*V[V_siz].y;

    sol=fabs(sol);

    return sol/2;
}

void draw_line (punct A , punct B , int ind_A , int ind_B , int sens)
{
    int i;
    double aux;
    P1=A; P2=B;
    st_siz=0;
    dr_siz=0;
    for (i=1;i<=n;i++)
    {
        if (i!=ind_A && i!=ind_B)
        {
          aux=cross_product(a[i],A,B);
          if (aux<eps)
          {
           st[++st_siz]=a[i];
           parte[i]=0;
          }
          if (aux>eps)
          {
           dr[++dr_siz]=a[i];
           parte[i]=1;
          }
        }
    }

    if (sens==1)
    {
      parte[ind_A]=0;
      parte[ind_B]=1;
      st[++st_siz]=A;
      dr[++dr_siz]=B;
    }

    if (sens==0)
    {
      parte[ind_A]=1;
      parte[ind_B]=0;
      st[++st_siz]=B;
      dr[++dr_siz]=A;
    }
}

bool convex_hull (punct V[nmax] , int V_siz , punct R[nmax] , int &R_siz)
{
    int h,auxsiz=0,stiv1_size,stiv2_size;
    sort(V+1,V+1+V_siz,cmp);

    stiv1[1]=V[1];
    stiv1[2]=V[2];
    stiv1_size=2;

    for (h=3;h<=V_siz;h++)
    {
        while (stiv1_size>=2 && cross_product(stiv1[stiv1_size-1],stiv1[stiv1_size],V[h])<eps)
         stiv1_size--;
        stiv1[++stiv1_size]=V[h];
    }

    stiv2_size=2;
    stiv2[1]=V[V_siz];
    stiv2[2]=V[V_siz-1];

    for (h=V_siz-2;h>=1;h--)
    {
        while (stiv2_size>=2 && cross_product(stiv2[stiv2_size-1],stiv2[stiv2_size],V[h])<eps)
         stiv2_size--;
        stiv2[++stiv2_size]=V[h];
    }

    for (h=1;h<=stiv1_size;h++)
       R[++auxsiz]=stiv1[h];

    for (h=2;h<stiv2_size;h++)
     R[++auxsiz]=stiv2[h];

     if (auxsiz!=V_siz)
      return 0;

    R_siz=auxsiz;

    return 1;
}

int main()
{
    int i,j,h;
    f>>n;
    for (i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;

    for (i=0;i<n;i++)
        fin[i]='V';
    fin[n]=NULL;

/*
    draw_line(a[6],a[3],6,3,0);
    for (i=1;i<=st_siz;i++)
     g<<st[i].x<<" "<<st[i].y<<'\n';
    g<<'\n';
    for (i=1;i<=dr_siz;i++)
     g<<dr[i].x<<" "<<dr[i].y<<'\n';
    g<<'\n';

    if (convex_hull(st,st_siz,ord_st,ord_st_siz));
     g<<'\n';

    if (convex_hull(dr,dr_siz,ord_dr,ord_dr_siz));
     g<<'\n';

    g<<arie(ord_st,ord_st_siz)<<" "<<arie(ord_dr,ord_dr_siz);
    create_answer();
    g<<'\n';
    g<<auxr;*/

    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
        {
           draw_line(a[i],a[j],i,j,0);
           if (convex_hull(st,st_siz,ord_st,ord_st_siz) && convex_hull(dr,dr_siz,ord_dr,ord_dr_siz))
           {
               ar1=arie(ord_st,ord_st_siz);
               ar2=arie(ord_dr,ord_dr_siz);
               if (fabs(ar1-ar2)==difmin)
               {
                   create_answer();
                   if (strcmp(auxr,fin)<0)
                     strcpy(fin,auxr);
               }

               if (fabs(ar1-ar2)<difmin)
               {
                   create_answer();
                   difmin=fabs(ar1-ar2);
                    strcpy(fin,auxr);
               }
           }

           draw_line(a[i],a[j],i,j,1);
           if (convex_hull(st,st_siz,ord_st,ord_st_siz) && convex_hull(dr,dr_siz,ord_dr,ord_dr_siz))
           {
               ar1=arie(ord_st,ord_st_siz);
               ar2=arie(ord_dr,ord_dr_siz);
               if (fabs(ar1-ar2)==difmin)
               {
                   create_answer();
                   if (strcmp(auxr,fin)<0)
                     strcpy(fin,auxr);
               }

               if (fabs(ar1-ar2)<difmin)
               {
                   create_answer();
                   difmin=fabs(ar1-ar2);
                    strcpy(fin,auxr);
               }
           }
        }

    g<<setprecision(1)<<fixed;
    g<<double(difmin)<<'\n';
    g<<fin;

    return 0;
}