Cod sursa(job #3248148)

Utilizator Eric_PaturanEric Paturan Eric_Paturan Data 10 octombrie 2024 21:30:28
Problema Gradina Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.6 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("gradina.in");
ofstream cout("gradina.out");
int n;
int ans=1e9;
string ret="";
struct points{
    int x,y,init;
};
points jos;
vector<points> v,a,b;
int orientation(points p, points q, points r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}
points penultimul(stack<points> &s)
{
    points aux;
    aux=s.top();
    s.pop();
    points ret=s.top();
    s.push(aux);
    return ret;
}
int distance(points A,points B)
{
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
bool panta(points A,points B)
{
    int o=orientation(jos,A,B);
    if(o==0)
    {
        return (distance(jos,B)>=distance(jos,A))?true:false;
    }
    return (o==2)?true:false;
}
int arie(points A,points B,points C)
{
    return A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}
int main()
{
    cin>>n;
    v.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i].x>>v[i].y;
        v[i].init=i;
    }
    for(int i=1;i<n;i++)
    {
        if(v[i].y<v[0].y)
            swap(v[0],v[i]);
    }
    jos=v[0];
    sort(v.begin() , v.end() , panta);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i!=j)
            {
                string cur;
                cur.resize(n);
                points p1=v[i] , p2=v[j];
                if(p1.y<p2.y)
                    swap(p1,p2);
                if(p1.y==p2.y && p1.x<p2.x)
                    swap(p1,p2);
                a.clear() , b.clear();
                for(int k=0;k<n;k++)
                {
                    if(k==i)
                        cur[v[i].init]='I' , a.push_back(v[i]);
                    if(k==j)
                        cur[v[j].init]='V'  , b.push_back(v[j]);
                    if(k!=i && k!=j)
                    {
                        if(orientation(p1,p2,v[k])==1)
                            a.push_back(v[k]) , cur[v[k].init]='I';
                        else b.push_back(v[k]) , cur[v[k].init]='V';
                    }
                }
                if(a.size()<3 || b.size()<3)
                    continue;
                stack<points> s;
                s.push(a[0]);
                s.push(a[1]);
                s.push(a[2]);
                for(int k=3;k<a.size();k++)
                {
                    while(s.size()>1 && orientation(penultimul(s),s.top() , a[k])!=2)
                        s.pop();
                    s.push(a[k]);
                }
                vector<points> convex1,convex2;
                while(!s.empty())
                {
                    convex1.push_back(s.top());
                    s.pop();
                }
                s.push(b[0]);
                s.push(b[1]);
                s.push(b[2]);
                for(int k=3;k<b.size();k++)
                {
                    while(s.size()>1 && orientation(penultimul(s),s.top() , b[k])!=2)
                        s.pop();
                    s.push(b[k]);
                }
                while(!s.empty())
                {
                    convex2.push_back(s.top());
                    s.pop();
                }
                points pct=convex1[0];
                int arie1=0;
                if(convex1.size()==3)
                    arie1=arie(convex1[0],convex1[1],convex1[2]);
                else
                    for(int k=1;k<a.size()-1;k++)
                    {
                        arie1+=arie(pct,convex1[k],convex1[k+1]);
                    }
                pct=convex2[0];
                int arie2=0;
                if(convex2.size()==3)
                    arie2=arie(convex2[0],convex2[1],convex2[2]);
                else
                    for(int k=1;k<convex2.size()-1;k++)
                    {
                        arie2+=arie(pct,convex2[k],convex2[k+1]);
                    }
                if(arie1<0)
                    arie1*=(-1);
                if(arie2<0)
                    arie2*=(-1);
                int dif=abs(arie1-arie2);
                if(dif<ans)
                {
                    ans=dif;
                    ret=cur;
                }
                else if(dif==ans)
                {
                    ret=min(ret,cur);
                }
            }
        }
    }
    double ans1=ans;
    double fin=1.0*(ans1/2);
    cout<<fixed<<setprecision(1)<<fin<<'\n';
    cout<<ret;
    return 0;
}