Pagini recente » Cod sursa (job #671680) | Cod sursa (job #1514808) | Cod sursa (job #2283679) | Cod sursa (job #1539175) | Cod sursa (job #2883844)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct punct
{
double x,y;
int id;
};
punct v[251];
double arie(double xa,double ya,double xb,double yb,double xc,double 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;
}
int viz[251];
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++;
}
for (int i=2; i<k; i++) viz[stiva[i].id]=1;
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=2; i<k1; i++) if (viz[stiva1[i].id]==1)
{
k=0;
ks=0;
k1=0;
}
else viz[stiva1[i].id]=1;
for (int i=1; i<=k; i++) st[++ks]=stiva[i];
for (int i=k1-1; i>=2; i--) st[++ks]=stiva1[i];
viz[v[x].id]=1;
viz[v[y].id]=1;
/*for (int i=1; i<=n; i++) cout << viz[i] <<" ";
cout <<"\n";
for (int i=1; i<=ks; i++) cout << st[i].x<<" "<<st[i].y <<"\n";*/
}
double cmp(punct a,punct b)
{
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
double 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 (double i=1;i<=n;i++) cout << v[i].x <<" "<<v[i].y <<"\n";
double minn=1e9;
for (double i=3; i<=n-3; 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();
int ok=1;
for (int j=1; j<=n; j++) ok*=viz[j];
for (int j=1; j<=n; j++)
{
viz[j]=0;
}
//cout << a1 <<" "<<a2<<"\n";
if (abs(a1-a2)<minn&&ok==1)
{
minn=abs(a1-a2);
for (int j=1; j<=n; j++)
{
ans[j]=0;
viz[j]=0;
}
for (int j=1; j<=ks; j++)
{
ans[st[j].id]=1;
}
}
}
double 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";
}
}