Cod sursa(job #2408373)

Utilizator sichetpaulSichet Paul sichetpaul Data 17 aprilie 2019 21:12:55
Problema Gradina Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 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,x[300],y[300];int nr,st1[300],st2[300],p[300];
char curr[255],ans[255];
struct point{
   ll x,y;int pos;
};
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]=1,st1[2]=2;
    for (i=3;i<=nr;++i) {
        while (nr1>=2 && cross_product(st1[nr1-1],st1[nr1],i)>0)
            --nr1;
        st1[++nr1]=i;
    }

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

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

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


      for (i=2;i<len;++i)
         ans+=abs(cross_product(p[1],p[i],p[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>>x[i]>>y[i];

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

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

        ++nr;
        if (lap==1) curr[i]='I',v[nr].x=x[i],v[nr].y=y[i],v[nr].pos=i;
        else curr[i]='V',v[nr].x=x[j],v[nr].y=y[j],v[nr].pos=j;
        sort(v+1,v+nr+1,cmp);
        area1=calc();
        if (nr<3) area1=0;

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

        ++nr;
        if (lap==2) curr[j]='I',v[nr].x=x[i],v[nr].y=y[i],v[nr].pos=i;
        else curr[j]='V',v[nr].x=x[j],v[nr].y=y[j],v[nr].pos=j;
        sort(v+1,v+nr+1,cmp);
        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;
}