Cod sursa(job #2163552)

Utilizator patcasrarespatcas rares danut patcasrares Data 12 martie 2018 18:51:12
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define DN 255
#define x first
#define y second
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
int n,nr1,nr2,f[DN];
int r[DN],p,st[DN],top;
char c[DN];
typedef pair<double,double>pii;
double rez=1e18,t;
pii z[DN],a[DN],b[DN];
double det(pii A,pii B,pii C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
double ve(pii a[DN],int n)
{
    double s=0;
    top=2;
    st[1]=1;
    st[2]=2;
    for(int i=3;i<=n;i++)
    {
        while(top>1&&det(a[st[top-1]],a[st[top]],a[i])<0)
            top--;
        top++;
        st[top]=i;
    }
    for(int i=n-1;i>=1;i--)
    {
        while(top>1&&det(a[st[top-1]],a[st[top]],a[i])<0)
            top--;
        top++;
        st[top]=i;
    }
    for(int i=1;i<top;i++)
        s+=det(a[0],a[st[i]],a[st[i+1]]);
    s/=2;
    if(top!=n+1)
        return 1e18;
    return s;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>z[i].x>>z[i].y;
    sort(z+1,z+n+1);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            nr1=nr2=0;
            if(i==1||det(z[1],z[i],z[j])<0)
            {
                for(int h=1;h<=n;h++)
                    if(h==i||det(z[h],z[i],z[j])<0)
                    {
                        f[h]=0;
                        nr1++;
                        a[nr1]=z[h];
                    }
                    else
                    {
                        f[h]=1;
                        nr2++;
                        b[nr2]=z[h];
                    }
            }
            else
            {
                for(int h=1;h<=n;h++)
                    if(h==i||det(z[h],z[i],z[j])<0)
                    {
                        f[h]=1;
                        nr2++;
                        b[nr2]=z[h];
                    }
                    else
                    {
                        f[h]=0;
                        nr1++;
                        a[nr1]=z[h];
                    }
            }
            if(min(nr1,nr2)<3)
                continue;
            t=abs(ve(a,nr1)-ve(b,nr2));
            if(t==rez)
            {
                p=1;
                for(int h=1;h<=n;h++)
                    if(f[h]<r[h])
                        break;
                    else
                        if(f[h]>r[h])
                        {
                            p=0;
                            break;
                        }
                if(p)
                    for(int h=1;h<=n;h++)
                        r[h]=f[h];
                continue;
            }
            if(t<rez)
            {
                rez=t;
                for(int h=1;h<=n;h++)
                    r[h]=f[h];
            }
        }
    for(int i=1;i<=n;i++)
        if(r[i]==0)
            c[i]='I';
        else
            c[i]='V';
    fout<<fixed<<setprecision(1)<<rez<<'\n';
    for(int i=1;i<=n;i++)
        fout<<c[i];
}