Cod sursa(job #1262593)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 13 noiembrie 2014 12:45:49
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <iomanip>

#define x first
#define y second
#define LL long long

using namespace std;

const int nmax=250;

int n;

LL Min=(1<<30);
string Ans;
char c[2][nmax+5];

pair < int, int > a[nmax+5];
vector < int > sol1, sol2, sol_i, sol_v;
int ind[nmax+5];
bool viz[nmax+5];

bool cmp(int ind1, int ind2)
{
	return a[ind1].x < a[ind2].x || (a[ind1].x == a[ind2].x && a[ind1].y < a[ind2].y);
}

int ll;

LL myabs(LL x)
{
	if(x>0)return x;
	return -x;
}

inline LL cp(pair < int, int> A, pair < int, int > B , pair < int, int > C)
{
    return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}

bool cmp2(int ind1, int ind2)
{
	return cp(a[ll], a[ind1], a[ind2])>0;
}

LL area(vector < int > v)
{
	int A=0;
	for(int i=1;i<v.size()-1;i++)
		A+=cp(a[v[0]], a[v[i]], a[v[i+1]]);
	return myabs(A);
}

void convex_hull(vector <int> &ind, vector <int> &sol)
{
	ll=ind[0];
	sort(ind.begin(), ind.end(), cmp2);
	if(ind.size()<3)return;
	sol.clear();
	sol.push_back(ind[0]);
	sol.push_back(ind[1]);
	memset(viz, 0, sizeof(viz));
	viz[ind[1]]=true;
	for(int i=2;i<ind.size();i++)
	{
		if(viz[ind[i]])continue;
		while(sol.size()>=2 && cp(a[sol[sol.size()-2]], a[sol[sol.size()-1]], a[ind[i]])<0)
		{
			viz[sol[sol.size()-1]]=false;
			sol.pop_back();
		}
		viz[ind[i]]=true;
		sol.push_back(ind[i]);
	}
}

string make_string(vector < int > v, vector < int > i)
{
	for(int j=0;j<v.size();j++)
	{
		c[0][v[j]]='I';
		c[1][v[j]]='V';
	}
	for(int j=0;j<i.size();j++)
	{
		c[0][i[j]]='V';
		c[1][i[j]]='I';
	}
	string s1(c[0]+1);
	string s2(c[1]+1);
	return min(s1, s2);
}

int main()
{
    freopen("gradina.in", "r", stdin);
    ofstream out("gradina.out");
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
		ind[i]=i;
	}
	sort(ind+1, ind+n+1, cmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			sol1.clear();
			sol2.clear();
			for(int k=1;k<=n;k++)
			{
				if(k==i) sol1.push_back(ind[k]);
				else if(k==j) sol2.push_back(ind[k]);
				else if(cp(a[ind[i]], a[ind[j]], a[ind[k]])>0)
					sol1.push_back(ind[k]);
				else sol2.push_back(ind[k]);
			}
			sol_i.clear();
			sol_v.clear();
			convex_hull(sol1, sol_i);
			convex_hull(sol2, sol_v);
			if(sol1.size()==sol_i.size() && sol2.size()==sol_v.size())
			{
				LL Ai=area(sol_i);
				LL Av=area(sol_v);
				LL dif=myabs(Ai-Av);
				if(dif<Min)
				{
					Min=dif;
					Ans=make_string(sol_i, sol_v);
				}
				else if(dif==Min)
				{
					Ans=min(Ans, make_string(sol_i, sol_v));
				}
			}
		}
	}
	out << fixed << setprecision(1) << Min*0.5 << "\n" << Ans << "\n";
    return 0;
}