Cod sursa(job #3248071)

Utilizator Eric_PaturanEric Paturan Eric_Paturan Data 10 octombrie 2024 19:39:08
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.67 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("gradina.in");
ofstream cout("gradina.out");
int n,cnt=1;
float ans=1e9;
string ret="";
struct points{
    int x,y;
};
points jos1,jos2;
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 panta1(points A,points B)
{
    int o=orientation(jos1,A,B);
    if(o==0)
    {
        return (distance(jos1,B)>=distance(jos1,A))?true:false;
    }
    return (o==2)?true:false;
}
bool panta2(points A,points B)
{
    int o=orientation(jos2,A,B);
    if(o==0)
    {
        return (distance(jos2,B)>=distance(jos1,A))?true:false;
    }
    return (o==2)?true:false;
}
float arie(points A,points B,points C)
{
    float ret=(A.x*(B.y-C.y)+B.x*(C.y-A.y)+C.x*(A.y-B.y))/2;
    return ret;
}
int main()
{
    cin>>n;
    v.resize(n);
    for(int i=0;i<n;i++)
        cin>>v[i].x>>v[i].y;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i!=j)
            {
                string cur="";
                points p1=v[i] , p2=v[j];
                if(p1.y>p2.y)
                    swap(p1,p2);
                else 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+='I';
                    if(k==j)
                        cur+='V';
                    if(k!=i && k!=j)
                    {
                        if(orientation(p1,p2,v[k])==1)
                            a.push_back(v[k]) , cur+='I';
                        else b.push_back(v[k]) , cur+='V';
                    }
                }
                a.push_back(v[i]);
                b.push_back(v[j]);
                if(a.size()<3 || b.size()<3)
                    continue;
                for(int k=1;k<a.size();k++)
                {
                    if(a[k].y<a[0].y)
                        swap(a[0],a[k]);
                }
                for(int k=1;k<b.size();k++)
                {
                    if(b[k].y<b[0].y)
                        swap(b[0],b[k]);
                }
                jos1.x=a[0].x , jos1.y=a[0].y;
                jos2.x=b[0].x , jos2.y=b[0].y;
                sort(a.begin() , a.end() , panta1);
                sort(b.begin() , b.end() , panta2);
                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=a[0];
                float arie1=0;
                for(int k=1;k<a.size()-1;k++)
                {
                    arie1+=arie(pct,a[k],a[k+1]);
                }
                pct=b[0];
                float arie2=0;
                for(int k=1;k<b.size()-1;k++)
                {
                    arie2+=arie(pct,b[k],b[k+1]);
                }
                float dif=arie1-arie2;
                if(dif<0)
                    dif*=(-1);
                if(dif<ans)
                {
                    ans=dif;
                    ret=cur;
                }
                else if(dif==ans)
                {
                    ret=min(ret,cur);
                }
            }
        }
    }
    cout<<fixed<<setprecision(1)<<ans<<'\n';
    cout<<ret;
    return 0;
}