Cod sursa(job #1922523)

Utilizator diacacmmDiac Adrian diacacmm Data 10 martie 2017 17:47:11
Problema Gradina Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.28 kb
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
long long minim=(1LL<<62);
struct punct
{
    int x,y,z;
};

punct v[251],v1[251],v2[251];
bool sol1[251],sol[251];
bool cmp(punct a,punct b)
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y<b.y;
}

long long cp(punct a,punct b,punct c)
{
    return 1LL*a.x*b.y-1LL*a.y*b.x+1LL*b.x*c.y-1LL*b.y*c.x+1LL*c.x*a.y-1LL*c.y*a.x;
}

int ccw(punct a,punct b,punct c)
{
    if(cp(a,b,c)>0)
        return 1;
    if(cp(a,b,c)<0)
        return -1;
    return 0;
}

bool cmp1(punct a,punct b)
{
    return ccw(v1[1],a,b)>0;
}

bool cmp2(punct a,punct b)
{
    return ccw(v2[1],a,b)>0;
}

int main()
{
    ifstream f("gradina.in");
    ofstream g("gradina.out");
    int n,i,j,k,nr1,nr2;
    long long arie1,arie2;
    f>>n;
    for(i=1; i<=n; ++i)
    {
        f>>v[i].x>>v[i].y;
        v[i].z=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1; i<n; ++i)
    {
        for(j=i+1; j<=n; ++j)
        {
            nr1=0;
            nr2=0;
            for(k=1; k<=n; ++k)
            {
                if(ccw(v[i],v[j],v[k])>0||k==i)
                {
                    v1[++nr1]=v[k];
                    sol1[v[k].z]=0;
                }
                else
                {
                    v2[++nr2]=v[k];
                    sol1[v[k].z]=1;
                }
            }
            if(nr1>=3&&nr2>=3)
            {
                sort(v1+2,v1+nr1+1,cmp1);
                sort(v2+2,v2+nr2+1,cmp2);
                bool ok=1;
                for(k=3; k<=nr1; ++k)
                {
                    if(ccw(v1[k-2],v1[k-1],v1[k])<1)
                    {
                        ok=0;
                        break;
                    }
                }
                if(ccw(v1[nr1-1],v1[nr1],v1[1])<1)
                    ok=0;
                if(ccw(v1[nr1],v1[1],v1[2])<1)
                    ok=0;
                if(ok)
                {
                    for(k=3; k<=nr2; ++k)
                    {
                        if(ccw(v2[k-2],v2[k-1],v2[k])<1)
                        {
                            ok=0;
                            break;
                        }
                    }
                    if(ccw(v2[nr2-1],v2[nr2],v2[1])<1)
                        ok=0;
                    if(ccw(v2[nr2],v2[1],v2[2])<1)
                        ok=0;
                    if(ok)
                    {
                        arie1=0;
                        arie2=0;
                        for(k=1; k<nr1; ++k)
                        {
                            arie1+=(1LL*v1[k].x*v1[k+1].y);
                            arie1-=(1LL*v1[k].y*v1[k+1].x);
                        }
                        arie1+=(1LL*v1[nr1].x*v1[1].y);
                        arie1-=(1LL*v1[1].x*v1[nr1].y);
                        if(arie1<0)
                            arie1*=(-1);
                        for(k=1; k<nr2; ++k)
                        {
                            arie2+=(1LL*v2[k].x*v2[k+1].y);
                            arie2-=(1LL*v2[k].y*v2[k+1].x);
                        }
                        arie2+=(1LL*v2[nr2].x*v2[1].y);
                        arie2-=(1LL*v2[1].x*v2[nr2].y);
                        if(arie2<0)
                            arie2*=(-1);
                        long long arie=arie1-arie2;
                        if(arie<0)
                            arie*=(-1);
                        if(arie<minim)
                        {
                            minim=arie;
                            for(k=1; k<=n; ++k)
                            {
                                sol[k]=sol1[k];
                            }
                        }
                    }
                }
            }
        }
    }
    if(minim%2==0)
        g<<minim/2<<".0\n";
    else
        g<<minim/2<<".5\n";
    if(sol[1]==0)
    {
        for(i=1;i<=n;++i)
        {
            if(sol[i]==0)
                g<<"I";
            else
                g<<"V";
        }
    }
    else
    {
        for(i=1;i<=n;++i)
        {
            if(sol[i]==0)
                g<<"V";
            else
                g<<"I";
        }
    }
    return 0;
}