Pagini recente » Cod sursa (job #2924200) | Cod sursa (job #1321647) | Cod sursa (job #854319) | Cod sursa (job #1311427) | Cod sursa (job #2981273)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
ll n,auxil;
double tot=LLONG_MAX / 2;
struct pct
{
ll x,y;
int t;
} a[255];
bool cmp(pct X,pct Y)
{
if(X.x==Y.x)
return X.y<Y.y;
return X.x<Y.x;
}
vector<int>ion;
vector<int>vasile;
int det(pct x,pct y,pct z)
{
return (y.x-x.x)*(z.y-x.y)-(z.x-x.x)*(y.y-x.y);
}
bool cmp2(int A,int B)
{
return (det(a[auxil],a[A],a[B])>0.0);
}
double triunghi(int x,int y,int z)
{
return det(a[x],a[y],a[z])/2.0;
}
double arie_polig(vector<int>r,int m)
{
r.push_back(r[0]);
double S=0;
for(int i=1; i<m; i++)
S+=triunghi(r[0],r[i],r[i+1]);
return S;
}
bool check(vector<int>&r,int m)
{
auxil=r[0];
sort(r.begin()+1,r.end(),cmp2);
for(int i=2; i<m; i++)
if(det(a[r[i-2]],a[r[i-1]],a[r[i]])<=0)
return 0;
return 1;
}
char sol[500];
int main()
{
f>>n;
for(int i=1; i<=n; i++)
f>>a[i].x>>a[i].y,a[i].t=i;
sort(a+1,a+n+1,cmp);
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
{
ion.clear();
vasile.clear();
for(int k=1; k<=n; k++)
{
if(det(a[i],a[j],a[k])>0)
{
ion.push_back(k);
}
else
{
vasile.push_back(k);
}
}
bool ok=1;
if(ion.size()>=3&&vasile.size()>=3)
{
if(check(ion,ion.size())&&check(vasile,vasile.size()))
{
double red=arie_polig(ion,ion.size());
double grn=arie_polig(vasile,vasile.size());
double dif=abs(red-grn);
if(tot>=dif)
{
tot=dif;
for(auto x:vasile)
if(a[x].t==1)
ok=0;
for(auto x:vasile)
if(ok==0)
sol[a[x].t]='I';
else
sol[a[x].t]='V';
for(auto x:ion)
if(!ok==0)
sol[a[x].t]='I';
else
sol[a[x].t]='V';
}
}
}
}
g<<setprecision(1)<<fixed<<tot;
g<<'\n';
for(int w=1; w<=n; w++)
g<<sol[w];
return 0;
}