Cod sursa(job #3245976)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 1 octombrie 2024 12:13:40
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <bits/stdc++.h>

using namespace std;
int rez[251],sol[251];
double dmin=1e9;
struct ura
{
    int ord,x,y,t;
}v[251];
bool cmp(ura a, ura b)
{
    if(a.x<b.x)
        return true;
    if(a.x>b.x)
        return false;
    return a.y<b.y;
}
bool arie(int i, int j, int k)
{
    return 1LL*v[i].x*(v[j].y-v[k].y)+1LL*v[j].x*(v[k].y-v[i].y)+1LL*v[k].x*(v[i].y-v[j].y)>0;
}
int st1[251],st2[251],k1,k2;
int st[251],k,tip[251];
double area(int i, int j, int k)
{
    return double(1LL*v[i].x*(v[j].y-v[k].y)+1LL*v[j].x*(v[k].y-v[i].y)+1LL*v[k].x*(v[i].y-v[j].y))/2;
}
double convex(int p[], int n)
{
    int i;
    for(i=2;i<n;i++)
    {
        if(arie(p[1],p[n],p[i]))
            tip[i]=1;
        else
            tip[i]=2;
    }
    tip[n]=2;
    tip[1]=1;
    k=1;
    st[1]=p[1];
    for(i=2;i<=n;i++)
    {
        if(tip[i]==2)
        {
            if(k>1&&!arie(st[k-1],st[k],p[i]))
                return -1;
            k++;
            st[k]=p[i];
        }
    }
    for(i=n-1;i>=1;i--)
    {
        if(tip[i]==1)
        {
            if(k>1&&!arie(st[k-1],st[k],p[i]))
                return -1;
            k++;
            st[k]=p[i];
        }
    }
    k--;
    double sum=0;
    for(i=2;i<k;i++)
    {
        sum+=area(st[1],st[i],st[i+1]);
    }
    return sum;
}
void calc(int n)
{
    k1=k2=0;
    int i;
    for(i=1;i<=n;i++)
    {
        if(v[i].t==1)
            st1[++k1]=i;
        else
            st2[++k2]=i;
    }
    if(k1<3||k2<3)
        return;
    double s1=convex(st1,k1),s2=convex(st2,k2);
    if(s1<0||s2<0)
        return;
    if(abs(s1-s2)<dmin)
    {
        dmin=abs(s1-s2);
        for(i=1;i<=n;i++)
            rez[v[i].ord]=v[i].t;
    }
    else
    if(abs(s1-s2)==dmin)
    {
        for(i=1;i<=n;i++)
            sol[v[i].ord]=v[i].t;
        int nr1,nr2;
        for(i=2,nr1=1,nr2=1;i<=n;i++)
        {
            if(rez[i]!=rez[i-1])
                nr1=1;
            else
                nr1++;
            if(sol[i]!=sol[i-1])
                nr2=1;
            else
                nr2++;
            if(nr1>nr2)
                return ;
            if(nr2>nr1)
                i=n;
        }
        for(i=1;i<=n;i++)
            rez[i]=sol[i];
    }
}
int main()
{
    freopen ("gradina.in","r",stdin);
    freopen ("gradina.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].ord=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                if(k!=i&&k!=j)
                {
                    if(arie(i,j,k))
                        v[k].t=1;///stanga
                    else
                        v[k].t=2;///dreapta
                }
            }
            v[i].t=1;
            v[j].t=2;
            calc(n);
            v[i].t=2;
            v[j].t=1;
            calc(n);
        }
    }
    cout<<fixed<<setprecision(1)<<dmin<<'\n';
    for(i=1;i<=n;i++)
        if(rez[i]==rez[1])
            cout<<'I';
        else
            cout<<'V';
    return 0;
}