Cod sursa(job #3249153)

Utilizator David_PoterasuDavid Poterasu David_Poterasu Data 14 octombrie 2024 23:02:29
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.69 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("gradina.in");
ofstream out("gradina.out");

int n, nv, nst1, nst2, pozitii[255];
double difmin=INT_MAX;
string rasp;

struct punct
{
  int x, y;
  bool tip;
}pct[255], v[255], st1[255], st2[255], cpct[255];

bool cmp(punct a, punct b)
{
  if(a.x==b.x)
    return a.y<b.y;
  return a.x<b.x;
}

void creare_pozitii()
{
  for(int i=1; i<=n; i++)
  {
    for(int j=1; j<=n; j++)
    {
      if(cpct[j].x==pct[i].x && cpct[j].y==pct[i].y)
      {
        pozitii[i]=j;
      }
    }
  }
}

bool verif_jos_pct(int a, int b, int c)
{
  int ax=pct[a].x, ay=pct[a].y, bx=pct[b].x, by=pct[b].y, cx=pct[c].x, cy=pct[c].y;
  return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<=0;
}

bool verif_jos_v(punct a, punct b, punct c)
{
  int ax=a.x, ay=a.y, bx=b.x, by=b.y, cx=c.x, cy=c.y;
  return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<=0;
}

void creare_stiva(punct (&st)[255], int &nst)
{
  st[++nst]=v[1];
  for(int i=2; i<=nv; i++)
  {
    if(verif_jos_v(v[1], v[nv], v[i]))
    {
      if(nst>=2 && verif_jos_v(st[nst-1], st[nst], v[i]))
      {
        nst=-1;
        return;
      }
      st[++nst]=v[i];
    }
  }
  int cnst=nst;
  for(int i=nv-1; i>=1; i--)
  {
    if(!verif_jos_v(v[1], v[nv], v[i]) || i==1)
    {
      if(nst>cnst && !verif_jos_v(st[nst], st[nst-1], v[i]))
      {
        nst=-1;
        return;
      }
      st[++nst]=v[i];
    }
  }
  nst--;
}

double arie_st(punct (&st)[255], int nst)
{
  long long arie=0;
  for(int i=2; i<nst; i++)
  {
    int ax=st[1].x, ay=st[1].y, bx=st[i].x, by=st[i].y, cx=st[i+1].x, cy=st[i+1].y;
    arie+=(ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax);
  }
  return (double)arie/2;
}

double dif()
{
  nv=0;
  for(int i=1; i<=n; i++)
  {
    if(pct[i].tip==0)
    {
      v[++nv]=pct[i];
    }
  }
  if(nv<3)
  {
    return INT_MAX;
  }
  nst1=0;
  creare_stiva(st1, nst1);

  nv=0;
  for(int i=1; i<=n; i++)
  {
    if(pct[i].tip==1)
    {
      v[++nv]=pct[i];
    }
  }
  if(nv<3)
  {
    return INT_MAX;
  }
  nst2=0;
  creare_stiva(st2, nst2);

  if(nst1==-1 || nst2==-1)
  {
    return INT_MAX;
  }

  if(abs(arie_st(st1, nst1)-arie_st(st2, nst2))<difmin)
  {
    rasp[1]='I';
    for(int i=2; i<=n; i++)
    {
      if(pct[i].tip==pct[1].tip)
      {
        rasp[pozitii[i]]='I';
      }
      else
      {
        rasp[pozitii[i]]='V';
      }
    }
  }
  else if(abs(arie_st(st1, nst1)-arie_st(st2, nst2))==difmin)
  {
    string rasp2;
    rasp2[1]='I';
    for(int i=2; i<=n; i++)
    {
      if(pct[i].tip==pct[1].tip)
      {
        rasp2[pozitii[i]]='I';
      }
      else
      {
        rasp2[pozitii[i]]='V';
      }
    }
    if(rasp2<rasp)
    {
      rasp=rasp2;
    }
  }

  return abs(arie_st(st1, nst1)-arie_st(st2, nst2));
}

int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
      in>>pct[i].x>>pct[i].y;
      cpct[i]=pct[i];
      pozitii[i]=1;
    }
    sort(pct+1, pct+n+1, cmp);

    creare_pozitii();
    for(int i=1; i<=n; i++)
      cout<<pozitii[i]<<" ";

    for(int i=1; i<n; i++)
    {
      for(int j=i+1; j<=n; j++)
      {
        for(int k=1; k<=n; k++)
        {
          if(k!=i && k!=j)
          {
            pct[k].tip=!verif_jos_pct(i, j, k);
          }
        }
        pct[i].tip=0;
        pct[j].tip=1;
        difmin=min(difmin, dif());
        //cout<<difmin<<' ';
        pct[i].tip=1;
        pct[j].tip=0;
        difmin=min(difmin, dif());
        //cout<<difmin<<'\n';
      }
    }

    out<<fixed<<setprecision(1)<<difmin<<'\n';
    for(int i=1; i<=n; i++)
    {
      out<<rasp[i];
    }
    return 0;
}