Pagini recente » Cod sursa (job #3255778) | Cod sursa (job #2717816) | Cod sursa (job #2509925) | Cod sursa (job #1359742) | Cod sursa (job #483130)
Cod sursa(job #483130)
#include<fstream>
#include<vector>
#include<cstdlib>
#define x first
#define y second
#define NMAX 300
#define inf 10000000.0
using namespace std;
typedef pair<long,long> pt;
vector< pt > p(NMAX),a(NMAX);
vector<long> st,uz(NMAX),m(NMAX);
pt w;
long n;
double Min=inf;
void cit()
{ifstream fin("gradina.in");
fin>>n;
for(long i=1;i<=n;++i)
fin>>a[i].x>>a[i].y;
fin.close();
}
long ec(pt p,pt q,pt w)
{long f,a,b,c;
a=p.y-q.y;
b=q.x-p.x;
c=-q.x*p.y+q.y*p.x;
f=a*w.x+b*w.y+c;
return f>0;
}
int cmp(pt a,pt b)
{return (a.y-w.y)*(b.x-w.x)<(a.x-w.x)*(b.y-w.y);
}
long double arie(pt a,pt b,pt c)
{return ((b.x-c.x)*(b.y-a.y)+(a.x-b.x)*(b.y-c.y));}
void hull(long n)
{long i,o;
o=1;
for(i=2;i<=n;++i)
if((p[i].x<p[o].x)||(p[i].x==p[o].x&&p[i].y<p[o].y))
o=i;
w=p[o];
p.erase(p.begin()+o);
--n;
p[0]=w;
sort(p.begin()+1,p.begin()+n+1,cmp);
st.push_back(0);
st.push_back(1);
for(i=2;i<=n;++i)
{ while(st.size()>1&&arie(p[st[st.size()-2]],p[st[st.size()-1]],p[i])<=0)
st.pop_back();
st.push_back(i);
}
}
long double aria(long n)
{long i;
long double s=0;
if(n<=1)
return 0;
else
for(i=1;i<=n-1;++i)
s+=fabsl(arie(p[st[0]],p[st[i]],p[st[i+1]]))/2;
return s;
}
void afis()
{long i,j,k,nr;
double si,sv,d;
ofstream fout("gradina.out");
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
{nr=0;
for(k=1;k<=n;++k)
uz[k]=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=1;
}
p[++nr]=a[i];p[++nr]=a[j];uz[i]=1;uz[j]=1;
st.clear();
if(nr>=3)
hull(nr);
si=aria(st.size()-1);
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=2;
}
st.clear();
if(nr>=3)
hull(nr);
sv=aria(st.size()-1);
d=sv-si;
if(fabsl(d)<Min)
{Min=fabsl(d);
for(k=1;k<=n;++k)
m[k]=uz[k];
}
if(fabsl(d)==Min)
{Min=fabsl(d);
if(uz<m)
for(k=1;k<=n;++k)
m[k]=uz[k];
}
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=1;
}
p[++nr]=a[i];uz[i]=1;
st.clear();
if(nr>=3)
hull(nr);
si=aria(st.size()-1);
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=2;
}
st.clear();
p[++nr]=a[j];uz[j]=2;
if(nr>=3)
hull(nr);
sv=aria(st.size()-1);
d=sv-si;
if(fabsl(d)<Min)
{Min=fabsl(d);
for(k=1;k<=n;++k)
m[k]=uz[k];
}
if(fabsl(d)==Min)
{Min=fabsl(d);
if(uz<m)
for(k=1;k<=n;++k)
m[k]=uz[k];
}
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=1;
}
p[++nr]=a[j];uz[j]=1;
st.clear();
if(nr>=3)
hull(nr);
si=aria(st.size()-1);
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=2;
}
st.clear();
p[++nr]=a[i];uz[i]=2;
if(nr>=3)
hull(nr);
sv=aria(st.size()-1);
d=sv-si;
if(fabsl(d)<Min)
{Min=fabsl(d);
for(k=1;k<=n;++k)
m[k]=uz[k];
}
if(fabsl(d)==Min)
{Min=fabsl(d);
if(uz<m)
for(k=1;k<=n;++k)
m[k]=uz[k];
}
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=1;
}
st.clear();
if(nr>=3)
hull(nr);
si=aria(st.size()-1);
nr=0;
for(k=1;k<=n;++k)
if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
{p[++nr]=a[k];
uz[k]=2;
}
st.clear();
p[++nr]=a[j];uz[j]=2;p[++nr]=a[i];uz[i]=2;
if(nr>=3)
hull(nr);
sv=aria(st.size()-1);
d=sv-si;
if(fabsl(d)<Min)
{Min=fabsl(d);
for(k=1;k<=n;++k)
m[k]=uz[k];
}
if(fabsl(d)==Min)
{Min=fabsl(d);
if(uz<m)
for(k=1;k<=n;++k)
m[k]=uz[k];
}
}
fout.precision(16);
fout<<Min<<'\n';
if(m[1]==2)
for(i=1;i<=n;++i)
if(m[i]==1)
m[i]=2;
else
m[i]=1;
for(i=1;i<=n;++i)
if(m[i]==1)
fout<<'I'<<" ";
else
fout<<'V'<<' ';
fout.close();
}
int main()
{cit();
afis();
return 0;
}