Cod sursa(job #2451902)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 28 august 2019 17:12:58
Problema Gradina Scor 30
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");

const int NMAX = 252;
const int INF = (1<<29);

struct punct
{
    int x,y;
};

punct a[NMAX],stanga[NMAX],dreapta[NMAX],pct[NMAX];
bool rasp[NMAX];

long double panta(punct a,punct b,punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

bool cmp(punct a,punct b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

bool cmp1(punct a,punct b)
{
    return panta(stanga[1],a,b)>=0;
}

bool cmp2(punct a,punct b)
{
    return panta(dreapta[1],a,b)>=0;
}

double arie_triunghi(int x1,int y1,int x2,int y2,int x3,int y3)
{
    return (double)(abs(x2*y3 - x1*y3 - x2*y1 - x3*y2 + x3*y1 + x1*y2))/2;
}

int main()
{
    int n;
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> a[i].x >> a[i].y;
    int coordx,coordy;
    long double minim=INF;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            int st=0,dr=0;
            stanga[++st]=a[i];
            dreapta[++dr]=a[j];
            for(int t=1;t<=n;t++)
            {
                if(t==i or t==j) continue;
                if(panta(a[i],a[j],a[t])>0)
                    stanga[++st]=a[t];
                else if(panta(a[i],a[j],a[t])<0)
                    dreapta[++dr]=a[t];
            }
            for(int t=1;t<=st;t++)
            {
                if(stanga[t].y==stanga[1].y)
                {
                    if(stanga[t].x<stanga[1].x) swap(stanga[t],stanga[1]);
                }
                else if(stanga[t].y<stanga[1].y) swap(stanga[t],stanga[1]);
            }
            for(int t=1;t<=dr;t++)
            {
                if(dreapta[t].y==dreapta[1].y)
                {
                    if(dreapta[t].x<dreapta[1].x) swap(dreapta[t],dreapta[1]);
                }
                else if(dreapta[t].y<dreapta[1].y) swap(dreapta[t],dreapta[1]);
            }
            sort(stanga+2,stanga+st+1,cmp1);
            sort(dreapta+2,dreapta+dr+1,cmp2);
            pct[1]=stanga[1];
            pct[2]=stanga[2];
            long long sz=2;
            for(long long t=3;t<=st;t++)
            {
                while(sz>=2 and panta(pct[sz-1],pct[sz],stanga[t])<0)
                    sz--;
                pct[++sz]=stanga[t];
            }
            double arie1=0;
            for(int t=2;t<=sz-1;t++)
            {
                arie1+=arie_triunghi(pct[1].x,pct[1].y,pct[t].x,pct[t].y,pct[t+1].x,pct[t+1].y);
            }
            pct[1]=dreapta[1];
            pct[2]=dreapta[2];
            sz=2;
            for(long long t=3;t<=dr;t++)
            {
                while(sz>=2 and panta(pct[sz-1],pct[sz],dreapta[t])<0)
                    sz--;
                pct[++sz]=dreapta[t];
            }
            double arie2=0;
            for(int t=2;t<=sz-1;t++)
            {
                arie2+=arie_triunghi(pct[1].x,pct[1].y,pct[t].x,pct[t].y,pct[t+1].x,pct[t+1].y);
            }
            if(abs(arie2-arie1)<minim)
            {
                minim=abs(arie2-arie1);
                coordx=i;
                coordy=j;
            }
        }
    }
    fout << fixed << setprecision(1) << minim << '\n';
    rasp[coordx]=1;
    for(int i=1;i<=n;i++)
    {
        if(i==coordx or i==coordy) continue;
        if(panta(a[coordx],a[coordy],a[i])>0)
            rasp[i]=1;
    }
    if(rasp[1]==0)
    {
        for(int i=1;i<=n;i++) if(rasp[i]==1) fout << "V";
                          else fout << "I";
    }
    else
    {
        for(int i=1;i<=n;i++) if(rasp[i]==1) fout << "I";
                          else fout << "V";
    }
    return 0;
}