Pagini recente » Cod sursa (job #1557967) | Cod sursa (job #458736) | Cod sursa (job #2667997) | Cod sursa (job #3226063) | Cod sursa (job #3245976)
#include <bits/stdc++.h>
using namespace std;
int rez[251],sol[251];
double dmin=1e9;
struct ura
{
int ord,x,y,t;
}v[251];
bool cmp(ura a, ura b)
{
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
return a.y<b.y;
}
bool arie(int i, int j, int k)
{
return 1LL*v[i].x*(v[j].y-v[k].y)+1LL*v[j].x*(v[k].y-v[i].y)+1LL*v[k].x*(v[i].y-v[j].y)>0;
}
int st1[251],st2[251],k1,k2;
int st[251],k,tip[251];
double area(int i, int j, int k)
{
return double(1LL*v[i].x*(v[j].y-v[k].y)+1LL*v[j].x*(v[k].y-v[i].y)+1LL*v[k].x*(v[i].y-v[j].y))/2;
}
double convex(int p[], int n)
{
int i;
for(i=2;i<n;i++)
{
if(arie(p[1],p[n],p[i]))
tip[i]=1;
else
tip[i]=2;
}
tip[n]=2;
tip[1]=1;
k=1;
st[1]=p[1];
for(i=2;i<=n;i++)
{
if(tip[i]==2)
{
if(k>1&&!arie(st[k-1],st[k],p[i]))
return -1;
k++;
st[k]=p[i];
}
}
for(i=n-1;i>=1;i--)
{
if(tip[i]==1)
{
if(k>1&&!arie(st[k-1],st[k],p[i]))
return -1;
k++;
st[k]=p[i];
}
}
k--;
double sum=0;
for(i=2;i<k;i++)
{
sum+=area(st[1],st[i],st[i+1]);
}
return sum;
}
void calc(int n)
{
k1=k2=0;
int i;
for(i=1;i<=n;i++)
{
if(v[i].t==1)
st1[++k1]=i;
else
st2[++k2]=i;
}
if(k1<3||k2<3)
return;
double s1=convex(st1,k1),s2=convex(st2,k2);
if(s1<0||s2<0)
return;
if(abs(s1-s2)<dmin)
{
dmin=abs(s1-s2);
for(i=1;i<=n;i++)
rez[v[i].ord]=v[i].t;
}
else
if(abs(s1-s2)==dmin)
{
for(i=1;i<=n;i++)
sol[v[i].ord]=v[i].t;
int nr1,nr2;
for(i=2,nr1=1,nr2=1;i<=n;i++)
{
if(rez[i]!=rez[i-1])
nr1=1;
else
nr1++;
if(sol[i]!=sol[i-1])
nr2=1;
else
nr2++;
if(nr1>nr2)
return ;
if(nr2>nr1)
i=n;
}
for(i=1;i<=n;i++)
rez[i]=sol[i];
}
}
int main()
{
freopen ("gradina.in","r",stdin);
freopen ("gradina.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int n,i,j,k;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
v[i].ord=i;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k!=i&&k!=j)
{
if(arie(i,j,k))
v[k].t=1;///stanga
else
v[k].t=2;///dreapta
}
}
v[i].t=1;
v[j].t=2;
calc(n);
v[i].t=2;
v[j].t=1;
calc(n);
}
}
cout<<fixed<<setprecision(1)<<dmin<<'\n';
for(i=1;i<=n;i++)
if(rez[i]==rez[1])
cout<<'I';
else
cout<<'V';
return 0;
}