Pagini recente » Borderou de evaluare (job #592977) | Borderou de evaluare (job #2884725) | Borderou de evaluare (job #2370076) | Borderou de evaluare (job #2530809) | Cod sursa (job #2844428)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
int n;
char aux[255], afis[255];
struct coords {
int x, y, ind;
}v[255], a[255], b[255];
bool cmp(coords a, coords b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
long long sp(coords a, coords b, coords c)
{
return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (c.x - a.x) * (b.y - a.y);
}
long long check(coords pct[], int len)
{
int nr_elem = 0;
coords stiva[255];
for(int i = 1; i <= len; i++)
{
while(nr_elem > 1 && sp(stiva[nr_elem - 1], stiva[nr_elem], pct[i]) < 0)
nr_elem--;
stiva[++nr_elem] = pct[i];
}
int cnt = nr_elem;
for(int i = len - 1; i >= 1; i--)
{
while(nr_elem > cnt && sp(stiva[nr_elem - 1], stiva[nr_elem], pct[i]) < 0)
{
nr_elem--;
}
stiva[++nr_elem] = pct[i];
}
if(nr_elem - 1 != len)
return -1;
if(sp(stiva[nr_elem - 2], stiva[nr_elem - 1], pct[1]) < 0)
return -1;
long long arie = 0;
for(int i = 1; i < nr_elem; i++)
arie = arie + (stiva[i].x * stiva[i+1].y - stiva[i+1].x * stiva[i].y);
return abs(arie);
}
bool strcompare(char s1[], char s2[])
{
for(int i = 1; i <= n; i++)
if(s1[i] > s2[i])
return 0;
return 1;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
{
fin >> v[i].x >> v[i].y;
v[i].ind = i;
}
sort(v + 1, v + n + 1, cmp);
check(v, n);
long long solmin =(1LL << 50);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
int cnta = 0, cntb = 0;
if(i==j)
continue;
for(int k = 1; k <= n; k++)
{
if(k == i)
{
a[++cnta] = v[k];
aux[v[k].ind] = 'I';
continue;
}
if(k == j)
{
b[++cntb] = v[k];
aux[v[k].ind] = 'V';
continue;
}
if((sp(v[i], v[j], v[k]) < 0) == (i > j))
{
a[++cnta] = v[k];
aux[v[k].ind] = 'I';
}
else
{
b[++cntb] = v[k];
aux[v[k].ind] = 'V';
}
}
if(cnta >=3 && cntb >= 3)
{
long long ariea = check(a, cnta);
long long arieb = check(b, cntb);
if(ariea >= 0 && arieb >= 0)
{
long long diff = abs(ariea - arieb);
if(diff <= solmin)
{
if(diff < solmin)
{
solmin = diff;
for(int i = 1; i <= n; i++)
afis[i] = aux[i];
}
else if(strcompare(aux, afis) == 1)
for(int i = 1; i <= n; i++)
afis[i] = aux[i];
}
}
}
}
}
fout << solmin / 2;
if(solmin % 2 == 0)
fout << ".0";
else fout <<".5";
fout << '\n';
if(afis[1] == 'V')
for(int i = 1; i <= n; i++)
afis[i] = 'V' + 'I' - afis[i];
for(int i = 1; i <= n; i++)
fout << afis[i];
return 0;
}
/*
.::////++ossss+. `++:``
-md+ohddhhhhhhMM/ oMMMNds+-`
`/dh` /M: `::://///mMo `hMm+oydmmNhs/-`
`:hNNM/ /M+ -:://///hMh `mMy/////+oydMNd`
`/dNmsoMd` :Mm.`.-:://///yMd`.MM+////////oNMy`
`/hNms///dM: :MN/--::::////oMm.-MN/////////dMN-
`/hNms/////oMd`-NN+::::::////+mNhhMh////////oMMo
yMNy////////dMhdNm/:::::://////+oss/////////mMm.
/NNs////////oddyo/::::::://////////////////sMM+
`+NMs//////////::::::::::://///////////////mMh`
`+NMs//////////::::::::::////////////////sMN:
`+MNo/////////::::::::::////////////////mMs`
`+MNo/////////:::::::::///////////////sMm.
oMN+////////:::::::::///////////////NM/
oMm+/////////+ooooosssssssssooo+//yMh
`oMm+////+osssssssssssssssssssssssNN.
`oMm+/osssssssssssssssssssssssssdM/
`+NmysssssssssssssssssssssssshNMs
-hMmhyssssssssssssssssyhdNNho-`
`-ohmNmmdddddddmmmmmhys+-``
``.-:://///::-..```
````..--:://++oosyyhh+`
``` .+osyyhdmmmmmmmmmmddddhyyshMM/
-sdmdy. -dMdhyyysooo+++/////::///:::yMm--os+-`
.dMMMMm-/mMmyhddd+::::::::::::omNmmdyohMmNMMMNo
+MMMMMNmMMMMMMMMMs::::::::::::sMMMMMMMNMMMMMMMm.
oMMMMMMMMMMMMMMNd/::::::::::::+mNMMMMMMMMMMMMMM:
/NMMMMMMMMNNmdyo/:::::/+++/::::/ohmmNMMMMMMMMMN-
`+hmNNdhyso+/::::::++:+ooo/::+::::/+oyhdmNNNNNy`
:mMy/:::::::::::/M+::::::::y::::::::://+oNMs`
`/NNs:/shhs/::::::+M:::::::::y:::::::/+//::sMm-
``````oNNo:oNMMMMNy:::::+M:::::::::y:::::+hNMMmo::hMh` ````
`.:oydddhhMm+:/yyyhmMMMy::::+M:::::::::y::::sNMMMMMMo:/dMs``/oosssso/-`
`+hNMNNNNNNNm/:::::://+ymN/:::+N:::::::::y:::sNmhso++sy::/mM+sMNNNNNNNNNh-
+MMNNNNNNNNNd/::::::+sso:o::::+N:::::::::y:::+/+ss+:::::::+NMNNNNNNNNNNNMy
+MMNNNNNNNNNNs::::::::::+ooo/:/+:::::::::dyyssso:::::::::::oNNNNNNNNNNNNMh
-MMMNNNNNNNNNmdddhhhyyyNds//:::::::::::::///+sdNmhhhhhhhddddNNNNNNNNNNNNMo
`dMMMMMMNNNNNNNNNNNNNNMm/::::::::::::::::::::::/mMNNNNNNNNNNNNNNNNNNMMMMN-
:NMMMMMMMMMMMMMMMMMMMMMmyo+//:::::::::::::://+odMMMMMMMMMMMMMMMMMMMMMMM+`
+MNNmNMMMMMMMMMMMMMMMMMMMMNNNNmddhhhhhddmNNNMMMMMMMMMMMMMMMMMMMMMMMNd/`
:mMdh/.-::/+ooosssyyyhhhhhhhhhddddddddddddddddddddhhhyyssooo+/:ydmMMm.
`oNMNhhy: `` `````````````````````````` `+hhhNMMm/`
-hMMNmhhhyo. `` ` `` -shhhhmNMMNs`
`+mMMNNmhhhhhyo-` `` . `` .:shhhhhhmNNNMMh.
.yMMNNNNmhhhhhhhhs+-.` `` . ` `-/oyhhhhhhhhmNNNNMMd:
:dMMNNNNNmhhhhhhhhhhhyso/:-.`` ` ``..-/+oyyhhhhhhhhhhhNNNNNNMMN+
`+NMMNNNNNNmhhhhhhhhhhhhhhhhyyssso+++//////://///+++osssyyhhhhhhhhhhhhhhhhhNNNNNNMMMN-
`sMMMMMNNNNNNhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhdNNNNNMMMMMs
.MMMMMMMMNNNNdhhhhhhhhhhhhhhhhhhhhhhhhhhhdddhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhmNNNMMMMMMN:
`+NMMMMMMMNNNmhhhhhhhhhhhhhhhhhhhhhhddmmmmmdhhhmmmmmdhhhhhhhhhhhhhhhhhhhhhdNNNMMMMMMm:
.yNMMMMMMMNNd/syhhhhhhhhhhhhhhhhdmmmmmmmdhhhhdmmmmdhsssssyyhhhhhhhhhhyyomNNMMMMMMh.
:dMMMMMMMMNs`.+shhhhhhhhhhysssssssyyhhhhhhhmmdysssssssssssyhhhhhhs/.`hNMMMMMMMs`
`+NMMMMMMMMh. .:+syhhhhsssssssssssssssshddssssssssssssssshys+:` `hMMMMMMMN/`
.sMMMMMMMMN/ `-:+oooosssssssssssssssssssssssooo+//:-.` -mMMMMMMMM/
:MMMMMMMMMd: ` ```....-----------...```` ` `sNMMMMMMMNMd`
`sMMmMMMMMMMMh/` .oNMMMMMMMNdhMM+
/MMmyhmMMMMMMMMmo- `` `:sNMMMMMMMNdhyymMN-
.mMmyyyyhmNMMMMMMMNdo:` `` `:odNMMMMMMMNdhyyyyyNMh`
`hMMysyyyyyhdNMMMMMMMMNmy+:.` `` `.:+hmNMMMMMMMMNdhyyyyssshMMo
oMMhssssyyyyyyhdNMMMMMMMMMNNmhs+/:---.-----://oyhmNNMMMMMMMMMNmhhyyyyysssssdMN:
:NMdsssssssyyyyyyhhmNMMMMMMMMMMMMMMNNNNmNNNNNMMMMMMMMMMMMMMMNdhyyyyyysssssssyNMd`
.mMNmdhyssssssyyyyyyyhdmNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNmhhyyyyyssssssssyyhNMMo
`yMNyyhdmmhyssssssyyyyyyyhhdmMMMMMMMMMMMMMMMMMMMMMMMMMMMmdhhyyyyyyssssssyyhmmdhyhMN-
+MMdsssssyhddhyysssssyyyyyyooshmNMMMMMMMMMMMMMMMMMMMNmhsooyyyyysssssyyddmmhyyssssmMd`
-NMmsssssssssyyhddhyyssssyysooooosydNNMMMMMMMMMMMMNdysooooosysssyyhdmmdhysssssssssyNMo
`dMNyssssssssssssssyhhdhhyys++++ooooooshmNMMMMMNmhsoooooo++++yhddddhyysssssssssssssshMN-
`sMMhsssssssssssssssssssyyhhdhysoooooooooooyhddysoooooooosyyhhhhyyssssssssssssssssssssmMd`
/MMmssssssssssssssssssssssssssyyhhdddddhhhhyyyhyyyhhhhhhhyysssssssssssssssssssssssssssyMMo`
-NMNysssssssssssssssssssssssssssssssssssyyyhhhhyyyysssssssssssssssssssssssssssssssssssssdMN-
/sso/////////////////////////////////////////////////////////////////////////////////////ss/
*/