Cod sursa(job #2408584)

Utilizator sichetpaulSichet Paul sichetpaul Data 18 aprilie 2019 10:00:53
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
    ifstream f("gradina.in");
    ofstream g("gradina.out");
ll best=-1,n,area1,area2,a,b,c;int nr,st1[300],st2[300],pos[300],p[300];
char curr[255],ans[255];
struct point{
   ll x,y;
};
point v[255];
bool cmp(point q1,point q2) {
   if (q1.x==q2.x) return q1.y<q2.y;
   return q1.x<q2.x;
}
int GetSign(ll ox,ll oy) {
   if (a*ox+b*oy+c<0) return -1;
   return 1;
}
ll cross_product(int p0,int p1,int p2) {
   return (v[p1].x-v[p0].x)*(v[p2].y-v[p0].y)-(v[p2].x-v[p0].x)*(v[p1].y-v[p0].y);
}
ll calc() {
    ll ans=0;int nr1,nr2,len=0,i;
    nr1=2,st1[1]=p[1],st1[2]=p[2];
    for (i=3;i<=nr;++i) {
        while (nr1>=2 && cross_product(st1[nr1-1],st1[nr1],p[i])>0)
            --nr1;
        st1[++nr1]=p[i];
    }

    nr2=2,st2[1]=p[nr],st2[2]=p[nr-1];
    for (i=nr-2;i>=1;--i) {
        while (nr2>=2 && cross_product(st2[nr2-1],st2[nr2],p[i])>0)
            --nr2;
        st2[++nr2]=p[i];
    }

      for (i=1;i<=nr1;++i)
          ++len,pos[len]=st1[i];
      for (i=2;i<nr2;++i)
          ++len,pos[len]=st2[i];

                if (nr1+nr2-2!=nr) return 0;


      for (i=2;i<len;++i)
         ans+=abs(cross_product(pos[1],pos[i],pos[i+1]));
      return ans;
}
bool smaller(int len) {
   for (int i=1;i<=len;++i)
      if (curr[i]>ans[i]) return 0;
      else if (curr[i]<ans[i]) return 1;
    return 0;
}
int main()
{    int i,j,k;

    f>>n;
    for (i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);

    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j) if (i!=j) {
        curr[i]='I',curr[j]='V';
        a=v[j].y-v[i].y,b=v[i].x-v[j].x,c=v[i].y*v[j].x-v[j].y*v[i].x;

    for (int lap=1;lap<=2;++lap) {
        nr=0;
        for (k=1;k<=n;++k)
             if (k!=i && k!=j) if (GetSign(v[k].x,v[k].y)==-1)
                  ++nr,curr[k]='I',p[nr]=k;

        ++nr;
        if (lap==1) curr[i]='I',p[nr]=i;
        else curr[i]='V',p[nr]=j;
        area1=calc();
        if (nr<3) area1=0;

        nr=0;
        for (k=1;k<=n;++k)
             if (k!=i && k!=j) if (GetSign(v[k].x,v[k].y)==1)
                  ++nr,curr[k]='V',p[nr]=k;

        ++nr;
        if (lap==2) curr[j]='I',p[nr]=i;
        else curr[j]='V',p[nr]=j;
        area2=calc();
        if (nr<3) area2=0;

        if (best==-1 && (area1 && area2)) {
               best=abs(area1-area2);
               for (k=1;k<=n;++k)
                  ans[k]=curr[k];
        }

        else if (abs(area1-area2)<best || (abs(area1-area2==best && smaller(n))))if (area1 && area2) {
                best=abs(area1-area2);
                for (k=1;k<=n;++k)
                    ans[k]=curr[k];
        }
    }
    }

       g<<best/2;
       if (best%2) g<<".5\n";
       else g<<".0\n";

       for (i=1;i<=n;++i)
           g<<ans[i];

    return 0;
}