Pagini recente » Cod sursa (job #1729180) | Cod sursa (job #1660800) | Cod sursa (job #2467932) | Cod sursa (job #579066) | Cod sursa (job #2530850)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <algorithm>
#include <fstream>
#include <iomanip>
#define nmax 255
using namespace std;
struct point{int x;int y;int pos;};
int n,semn;
double sol,soltrue=1<<30;
char ss[nmax],q[nmax];
point v[nmax],aux;
point a[nmax],b[nmax];
point a1[nmax],b1[nmax];
deque <point> d;
int det(const point &a,const point &b,const point &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmpsort(const point &a,const point &b)
{
if (a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
double poligon(point a[],int m)
{
int i,j=1,p;
d.clear();
d.push_back(a[1]);
for (i=2;i<m;i++) {
if (det(a[1],a[m],a[i])>=0)
d.push_back(a[i]);
else
d.push_front(a[i]);
}
d.push_back(a[m]);
int semn=det(d[d.size()-2],d[d.size()-1],d.front())>0;
for (i=0;i<=d.size()-3;i++) {
p=(det(d[i],d[i+1],d[i+2])>0);
if ((p>0)!=semn)
return 0;
}
double arie=0;
for (i=0;i<=d.size()-2;i++)
arie+=det(a[0],d[i],d[i+1]);
arie+=det(a[0],d[d.size()-1],d.front());
return abs(arie)/2.0;
}
int main()
{
int i,j=1,t;
ifstream f("gradina.in");
ofstream g("gradina.out");
f>>n;
for (i=1;i<=n;i++) {
f>>v[i].x>>v[i].y;
v[i].pos=i;
}
int m,m1,k,k1;
sort(v+1,v+n+1,cmpsort);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) {
if (i==j)
continue;
m=k=0;
for (t=1;t<=n;t++) {
if (t==i) {
a[++m]=v[t];
continue;
}
if (t==j) {
b[++k]=v[t];
continue;
}
if (det(v[i],v[j],v[t])>0)
a[++m]=v[t];
else
b[++k]=v[t];
}
if (m<3||k<3)
continue;
double s1=poligon(a,m);
double s2=poligon(b,k);
if (s1==0||s2==0)
continue;
sol=abs(s1-s2);
if (sol<=soltrue) {
for (t=1;t<=m;t++)
q[a[t].pos-1]='I';
for (t=1;t<=k;t++)
q[b[t].pos-1]='V';
if (q[0]=='V')
for (t=0;t<n;t++)
q[t]='I'+'V'-q[t];
if (sol<soltrue||(sol==soltrue&&strcmp(q,ss)==0)) {
soltrue=sol;
strcpy(ss,q);
}
}
}
g<<fixed<<setprecision(1)<<soltrue<<'\n'<<ss;
return 0;
}