Cod sursa(job #2981273)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 17 februarie 2023 16:58:37
Problema Gradina Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
ll n,auxil;
double tot=LLONG_MAX / 2;
struct pct
{
    ll x,y;
    int t;
} a[255];
bool cmp(pct X,pct Y)
{
    if(X.x==Y.x)
        return X.y<Y.y;
    return X.x<Y.x;
}
vector<int>ion;
vector<int>vasile;
int det(pct x,pct y,pct z)
{
    return (y.x-x.x)*(z.y-x.y)-(z.x-x.x)*(y.y-x.y);
}
bool cmp2(int A,int B)
{
    return (det(a[auxil],a[A],a[B])>0.0);
}
double triunghi(int x,int y,int z)
{
    return det(a[x],a[y],a[z])/2.0;
}
double arie_polig(vector<int>r,int m)
{
    r.push_back(r[0]);
    double S=0;
    for(int i=1; i<m; i++)
        S+=triunghi(r[0],r[i],r[i+1]);
    return S;
}
bool check(vector<int>&r,int m)
{
    auxil=r[0];
    sort(r.begin()+1,r.end(),cmp2);

    for(int i=2; i<m; i++)
        if(det(a[r[i-2]],a[r[i-1]],a[r[i]])<=0)
            return 0;
    return 1;
}
char sol[500];
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>a[i].x>>a[i].y,a[i].t=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            ion.clear();
            vasile.clear();
            for(int k=1; k<=n; k++)
            {
                if(det(a[i],a[j],a[k])>0)
                {
                    ion.push_back(k);
                }
                else
                {
                    vasile.push_back(k);
                }
            }
            bool ok=1;
            if(ion.size()>=3&&vasile.size()>=3)
            {
                if(check(ion,ion.size())&&check(vasile,vasile.size()))
                {
                    double red=arie_polig(ion,ion.size());
                    double grn=arie_polig(vasile,vasile.size());
                    double dif=abs(red-grn);
                    if(tot>=dif)
                    {
                        tot=dif;
                        for(auto x:vasile)
                            if(a[x].t==1)
                                ok=0;
                        for(auto x:vasile)
                            if(ok==0)
                            sol[a[x].t]='I';
                            else
                                sol[a[x].t]='V';
                        for(auto x:ion)
                            if(!ok==0)
                                sol[a[x].t]='I';
                            else
                                sol[a[x].t]='V';
                    }
                }
            }
        }
    g<<setprecision(1)<<fixed<<tot;
    g<<'\n';
    for(int w=1; w<=n; w++)
        g<<sol[w];
    return 0;
}