Pagini recente » Cod sursa (job #2201851) | Cod sursa (job #866947) | Cod sursa (job #1507071) | Cod sursa (job #2113071) | Cod sursa (job #1279758)
#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;
}