Cod sursa(job #2884065)

Utilizator alexxxxxxhalex alx alexxxxxxh Data 2 aprilie 2022 12:49:23
Problema Gradina Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct punct
{
    double x,y;
    int id;
};
punct v[251];
double arie(double xa,double ya,double xb,double yb,double xc,double yc)
{
    return (xa*yb+xb*yc+xc*ya-xc*yb-xb*ya-xa*yc)/2.0;
}
punct stiva[251];
punct stiva1[251];
int k,k1;
int n;
punct st[251];
int ks;
double arie_poligon()
{
    double ans=0;
    for (int i=1; i<=ks; i++)
    {
        ans+=st[i].x*st[i%ks+1].y-st[i].y*st[i%ks+1].x;
    }
    return ans/2.0;
}
int viz[251];
void inf(int x,int y)
{
    stiva[++k].x=v[x].x;
    stiva[k].y=v[x].y;
    stiva[k].id=v[x].id;
    int i=x+1;
    while (i<=y)
    {

        if (k<2)
        {
            if (arie(v[x].x,v[x].y,v[y].x,v[y].y,v[i].x,v[i].y)<=0)
            {
                stiva[++k].x=v[i].x;
                stiva[k].y=v[i].y;
                stiva[k].id=v[i].id;

            }
        }
        else
        {
            while (arie(stiva[k-1].x,stiva[k-1].y,stiva[k].x,stiva[k].y,v[i].x,v[i].y)<0 && k>=2)
            {

                k--;
            }

            stiva[++k].x=v[i].x;
            stiva[k].y=v[i].y;
            stiva[k].id=v[i].id;
        }

        i++;
    }
    for (int i=2; i<k; i++) viz[stiva[i].id]=1;

    stiva1[++k1].x=v[x].x;
    stiva1[k1].y=v[x].y;
    stiva1[k1].id=v[x].id;
    i=x+1;
    while (i<=y)
    {

        if (k1<2)
        {
            if (arie(v[x].x,v[x].y,v[y].x,v[y].y,v[i].x,v[i].y)>0)
            {
                stiva1[++k1].x=v[i].x;
                stiva1[k1].y=v[i].y;
                stiva1[k1].id=v[i].id;

            }
        }
        else
        {
            while (arie(stiva1[k1-1].x,stiva1[k1-1].y,stiva1[k1].x,stiva1[k1].y,v[i].x,v[i].y)>0 && k1>=2)
            {
                k1--;
            }
            stiva1[++k1].x=v[i].x;
            stiva1[k1].y=v[i].y;
            stiva1[k1].id=v[i].id;

        }

        i++;
    }
    for (int i=2; i<k1; i++) if (viz[stiva1[i].id]==1)
        {
            k=0;
            ks=0;
            k1=0;
        }
        else viz[stiva1[i].id]=1;
    for (int i=1; i<=k; i++) st[++ks]=stiva[i];
    for (int i=k1-1; i>=2; i--) st[++ks]=stiva1[i];
    viz[v[x].id]=1;
    viz[v[y].id]=1;
    /*for (int i=1; i<=n; i++) cout << viz[i] <<" ";
    cout <<"\n";
    for (int i=1; i<=ks; i++) cout << st[i].x<<" "<<st[i].y <<"\n";*/
}
double cmp(punct a,punct b)
{
    if (a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
double ans[251];
int main()
{
    fin >>n;
    for (int i=1; i<=n; i++)
    {
        fin >>v[i].x>>v[i].y;
        v[i].id=i;
    }
    sort(v+1,v+n+1,cmp);
    //for (double i=1;i<=n;i++) cout << v[i].x <<" "<<v[i].y <<"\n";

    double minn=1e9;
    for (double i=1; i<=n; i++)
    {
        k=0;
        ks=0;
        k1=0;
        inf(1,i);
        double a1=arie_poligon();
        k=0;
        ks=0;
        k1=0;
        inf(i+1,n);
        double a2=arie_poligon();
        int ok=1;
        for (int j=1; j<=n; j++) ok*=viz[j];
        for (int j=1; j<=n; j++)
        {
            viz[j]=0;
        }
        //cout << a1 <<"    "<<a2<<"\n";
        if (abs(a1-a2)<minn&&ok==1)
        {

            minn=abs(a1-a2);
            for (int j=1; j<=n; j++)
            {
                ans[j]=0;
                viz[j]=0;
            }
            for (int j=1; j<=ks; j++)
            {
                ans[st[j].id]=1;

            }
        }
    }
    double ok=ans[1];
    fout <<fixed<<setprecision(1)<< minn <<"\n";
    for (int i=1; i<=n; i++)
    {
        if (ans[i]==ok) fout << "I";
        else fout << "V";
    }
}