Pagini recente » Cod sursa (job #1050408) | Cod sursa (job #1845418) | Cod sursa (job #2625197) | Cod sursa (job #63058) | Cod sursa (job #3248148)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("gradina.in");
ofstream cout("gradina.out");
int n;
int ans=1e9;
string ret="";
struct points{
int x,y,init;
};
points jos;
vector<points> v,a,b;
int orientation(points p, points q, points r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0)? 1: 2;
}
points penultimul(stack<points> &s)
{
points aux;
aux=s.top();
s.pop();
points ret=s.top();
s.push(aux);
return ret;
}
int distance(points A,points B)
{
return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
bool panta(points A,points B)
{
int o=orientation(jos,A,B);
if(o==0)
{
return (distance(jos,B)>=distance(jos,A))?true:false;
}
return (o==2)?true:false;
}
int arie(points A,points B,points C)
{
return A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}
int main()
{
cin>>n;
v.resize(n);
for(int i=0;i<n;i++){
cin>>v[i].x>>v[i].y;
v[i].init=i;
}
for(int i=1;i<n;i++)
{
if(v[i].y<v[0].y)
swap(v[0],v[i]);
}
jos=v[0];
sort(v.begin() , v.end() , panta);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j)
{
string cur;
cur.resize(n);
points p1=v[i] , p2=v[j];
if(p1.y<p2.y)
swap(p1,p2);
if(p1.y==p2.y && p1.x<p2.x)
swap(p1,p2);
a.clear() , b.clear();
for(int k=0;k<n;k++)
{
if(k==i)
cur[v[i].init]='I' , a.push_back(v[i]);
if(k==j)
cur[v[j].init]='V' , b.push_back(v[j]);
if(k!=i && k!=j)
{
if(orientation(p1,p2,v[k])==1)
a.push_back(v[k]) , cur[v[k].init]='I';
else b.push_back(v[k]) , cur[v[k].init]='V';
}
}
if(a.size()<3 || b.size()<3)
continue;
stack<points> s;
s.push(a[0]);
s.push(a[1]);
s.push(a[2]);
for(int k=3;k<a.size();k++)
{
while(s.size()>1 && orientation(penultimul(s),s.top() , a[k])!=2)
s.pop();
s.push(a[k]);
}
vector<points> convex1,convex2;
while(!s.empty())
{
convex1.push_back(s.top());
s.pop();
}
s.push(b[0]);
s.push(b[1]);
s.push(b[2]);
for(int k=3;k<b.size();k++)
{
while(s.size()>1 && orientation(penultimul(s),s.top() , b[k])!=2)
s.pop();
s.push(b[k]);
}
while(!s.empty())
{
convex2.push_back(s.top());
s.pop();
}
points pct=convex1[0];
int arie1=0;
if(convex1.size()==3)
arie1=arie(convex1[0],convex1[1],convex1[2]);
else
for(int k=1;k<a.size()-1;k++)
{
arie1+=arie(pct,convex1[k],convex1[k+1]);
}
pct=convex2[0];
int arie2=0;
if(convex2.size()==3)
arie2=arie(convex2[0],convex2[1],convex2[2]);
else
for(int k=1;k<convex2.size()-1;k++)
{
arie2+=arie(pct,convex2[k],convex2[k+1]);
}
if(arie1<0)
arie1*=(-1);
if(arie2<0)
arie2*=(-1);
int dif=abs(arie1-arie2);
if(dif<ans)
{
ans=dif;
ret=cur;
}
else if(dif==ans)
{
ret=min(ret,cur);
}
}
}
}
double ans1=ans;
double fin=1.0*(ans1/2);
cout<<fixed<<setprecision(1)<<fin<<'\n';
cout<<ret;
return 0;
}