Cod sursa(job #1279758)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 30 noiembrie 2014 21:02:31
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<string>
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");

struct punct
{
    int x, y, pozin;
};
 
const int nmax = 300, inf = (1<<30);
punct v[nmax], v1[nmax], v2[nmax] ;
int n, l1, l2;
int st[nmax], srp[nmax];
int rasp = inf;
string aux, vrasp;
 
bool compar(punct a, punct b)
{
    if(a.x!=b.x)
        return a.x<b.x;
	else
		return a.y<b.y;
}

int det(punct a, punct b, punct c)
{
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

int modul(int x)
{
	if(x<0)
		return -x;
	else
		return x;
}

int arie(punct v[], int n)
{
    if(n<3)
        return 0 ;
 
    st[0] = 1;
    st[1] = 2;
 
    for(int i = 0; i<nmax; i++)
		srp[i] = 0;
 
    int pozact = 2, lst = 1, pas = 1, ar = 0;
 
    srp[2] = 1 ;
 
    while(srp[1]==0)
    {
        if(pozact==n)
            pas = -1;
 
        while(srp[pozact]==1)
            pozact += pas;
 
        while(lst!=0 && det(v[st[lst - 1]], v[st[lst]], v[pozact])>0)
            srp[st[lst--]] = 0 ;
 
		lst++;
        st[lst] = pozact;
        srp[pozact] = 1;
    }
 
    if(lst!=n)
        return 0;
 
    for(int i = 1; i<=lst; i++)
        ar += v[st[i - 1]].x * v[st[i]].y - v[st[i]].x * v[st[ i - 1 ]].y;
 
    return modul(ar);
}
 
int main()
{
	int player_unu=0;

    in>>n;
    for(int i = 1; i <= n; ++i )
    {
        in>>v[i].x>>v[i].y ;
        v[i].pozin = i;
    }
 
    sort(v + 1, v + n + 1, compar); 
    aux.resize(n);
 
    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=n; j++)
        {
            if(i!=j)
            {
                l1 = l2 = 0 ;
 
                for(int h = 1; h<=n; h++)
                {
                    if(h!=i && h!=j)
                    {
                        if(det(v[i], v[j], v[h])>0)
						{
							l1++;
                            v1[l1] = v[h];
						}
                        else
                        {
							l2++;
							v2[l2] = v[h];
						}

                    }

                    if(h==i)
					{
						l1++;
						v1[l1] = v[h];
					}

                    if(h==j)
					{
						l2++;
                        v2[l2] = v[h];
					}
                }
 
                int ab = arie(v1, l1), ac = arie(v2, l2);

                if(ab && ac)
                {
                    int act = modul(ab - ac);
 
                    if(act<=rasp)
                    {
                        for(int h = 1; h<=l1; h++)
                            aux[v1[h].pozin - 1] = 'I';
 
                        for(int h = 1; h<=l2; h++)
                            aux[v2[h].pozin - 1] = 'V';
 
                        if(act==rasp)
                            vrasp = min(vrasp, aux);
                        else
                            vrasp = aux;
 
                        rasp = act;
                    }
                }
            }
        }
    }
 
    out<<setprecision(1)<<fixed;
    out<<(double)rasp / 2.0<<'\n';
    out<<vrasp;
 
    return player_unu;
}