Cod sursa(job #3247854)

Utilizator Giurgea3000Giurgea Giurgea3000 Data 9 octombrie 2024 16:16:25
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>

using namespace std;

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

double difmin=-1;
char rasp[251];
int n,vf=0;

struct ura
{
    int x,y;
    short i;
    short arie=0;
} v[120002],s[120002];

int cearie(double xa, double ya, double xb, double yb, double xc, double yc)
{
    double ari;
    ari=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
    if(ari<0)
        return -1;
    if(ari>0)
        return 1;
    return 0;

}

bool sortare(ura a, ura b)
{
    if(a.x<b.x)
    {
        return true;
    }
    else if(a.x==b.x && a.y<b.y)
    {
        return true;
    }
    return false;
}

double arie(int st, int fi)
{
    double ari,atot=0;
    double xa=s[st].x,ya=s[st].y;
    for(int i=st + 1,j=st+2;j<=fi;i++,j++)
    {
        double xb=s[i].x;
        double yb=s[i].y;
        double xc=s[j].x;
        double yc=s[j].y;
        ari=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
        if(ari<0)
            ari*=-1;
        ari/=2.0;
        atot+=ari;
    }
    return atot;
}

void raspy( char r[],int x)
{
    int st,sf;
    char a[]={'V','\0'};
    char b[]={'I','\0'};
    for(int i=1;i<=n;i++)
    {
        strncpy(r+i-1,a,1);
        if(s[i].i==1)
        {
            if(i<=x)
            {
                st=1;
                sf=x;
            }
            else
            {
                st=x+1;
                sf=n;
            }
        }
    }
    for(int i=st;i<=sf;i++)
    {
        strncpy(r+s[i].i-1,b,1);
    }
}

void infasuratoare(int st, int dr)
{
    bool ver=0;
    vf=0;
    s[++vf]=v[st];
    for(int i=1; i<=n && ver==0; i++)
    {
        if(cearie(v[st].x,v[st].y,v[dr].x,v[dr].y,v[i].x,v[i].y)<0)
        {
            if(vf<2)
            {
                s[++vf]=v[i];
            }
            else
            {
                while(vf>=2 && cearie(s[vf-1].x,s[vf-1].y,s[vf].x,s[vf].y,v[i].x,v[i].y)==-1)
                {
                    ver=1;
                    break;
                    vf--;
                }
                vf++;
                s[vf]=v[i];
            }
        }
    }
    vf++;
    s[vf]=v[dr];
    int x=vf;
    for(int i=n; i>0 && ver==0; i--)
    {
        if(cearie(v[st].x,v[st].y,v[dr].x,v[dr].y,v[i].x,v[i].y)>0)
        {
            if(vf<=x+1)
            {
                s[++vf]=v[i];
            }
            else
            {
                while(vf>=x+1 && cearie(s[vf-1].x,s[vf-1].y,s[vf].x,s[vf].y,v[i].x,v[i].y)==-1)
                {
                    ver=1;
                    break;
                    vf--;
                }
                vf++;
                s[vf]=v[i];
            }
        }
    }
    if(ver==0)
    {
        double dif=-1;
        char raspuns[n];
        raspy(raspuns,x-1);
        if(arie(1,x-1)>arie(x,n))
        {
            dif=arie(1,x-1)-arie(x,n);
        }
        else
        {
            dif=arie(x,n)-arie(1,x-1);
        }
        if(difmin==-1)
        {
            difmin=dif;
            strcpy(rasp,raspuns);
        }
        else if(dif<difmin)
        {
            difmin=dif;
            strcpy(rasp,raspuns);
        }
        else if(difmin==dif)
        {
            if(strcmp(rasp,raspuns)>0)
            {
                strcpy(rasp,raspuns);
            }
        }
    }
}

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].i=i;
    }
    sort(v+1,v+n+1,sortare);
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            infasuratoare( i, j);
        }
    }
    cout<<fixed<<setprecision(1)<<difmin;
    cout<<'\n'<<rasp;
    return 0;
}