Pagini recente » Cod sursa (job #760709) | Cod sursa (job #1495817) | Cod sursa (job #2755709) | Cod sursa (job #545311) | Cod sursa (job #2883813)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct punct
{
int x,y,id;
};
punct v[251];
double arie(int xa,int ya,int xb,int yb,int xc,int yc)
{
return (xa*yb+xb*yc+xc*ya-xc*yb-xb*ya-xa*yc)/2.0;
}
punct stiva[251];
punct stiva1[251];
int k,k1;
int n;
punct st[251];
int ks;
double arie_poligon()
{
double ans=0;
for (int i=1; i<=ks; i++)
{
ans+=st[i].x*st[i%ks+1].y-st[i].y*st[i%ks+1].x;
}
return ans/2.0;
}
void inf(int x,int y)
{
stiva[++k].x=v[x].x;
stiva[k].y=v[x].y;
stiva[k].id=v[x].id;
int i=x+1;
while (i<=y)
{
if (k<2)
{
if (arie(v[x].x,v[x].y,v[y].x,v[y].y,v[i].x,v[i].y)<=0)
{
stiva[++k].x=v[i].x;
stiva[k].y=v[i].y;
stiva[k].id=v[i].id;
}
}
else
{
while (arie(stiva[k-1].x,stiva[k-1].y,stiva[k].x,stiva[k].y,v[i].x,v[i].y)<0 && k>=2)
{
k--;
}
stiva[++k].x=v[i].x;
stiva[k].y=v[i].y;
stiva[k].id=v[i].id;
}
i++;
}
stiva1[++k1].x=v[x].x;
stiva1[k1].y=v[x].y;
stiva1[k1].id=v[x].id;
i=x+1;
while (i<=y)
{
if (k1<2)
{
if (arie(v[x].x,v[x].y,v[y].x,v[y].y,v[i].x,v[i].y)>0)
{
stiva1[++k1].x=v[i].x;
stiva1[k1].y=v[i].y;
stiva1[k1].id=v[i].id;
}
}
else
{
while (arie(stiva1[k1-1].x,stiva1[k1-1].y,stiva1[k1].x,stiva1[k1].y,v[i].x,v[i].y)>0 && k1>=2)
{
k1--;
}
stiva1[++k1].x=v[i].x;
stiva1[k1].y=v[i].y;
stiva1[k1].id=v[i].id;
}
i++;
}
for (int i=1; i<=k; i++) st[++ks]=stiva[i];
for (int i=k1-1; i>=2; i--) st[++ks]=stiva1[i];
//for (int i=1;i<=ks;i++) cout << st[i].x<<" "<<st[i].y <<"\n";
}
int cmp(punct a,punct b)
{
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int ans[251];
int main()
{
fin >>n;
for (int i=1; i<=n; i++) {fin >>v[i].x>>v[i].y;v[i].id=i;}
sort(v+1,v+n+1,cmp);
//for (int i=1;i<=n;i++) cout << v[i].x <<" "<<v[i].y <<"\n";
double minn=1e9;
for (int i=3; i<=n-2; i++)
{
k=0;
ks=0;
k1=0;
inf(1,i);
double a1=arie_poligon();
k=0;
ks=0;
k1=0;
inf(i+1,n);
double a2=arie_poligon();
if (abs(a1-a2)<minn)
{
minn=abs(a1-a2);
for (int j=1;j<=n;j++) ans[j]=0;
for (int j=1;j<=ks;j++)
{
ans[st[j].id]=1;
}
}
}
int ok=ans[1];
fout <<fixed<<setprecision(1)<< minn <<"\n";
for (int i=1;i<=n;i++)
{
if (ans[i]==ok) fout << "I";
else fout << "V";
}
}