Pagini recente » Cod sursa (job #2679945) | Cod sursa (job #1687244) | Cod sursa (job #2091286) | Cod sursa (job #802640) | Cod sursa (job #2370076)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Punct
{
int x, y, ind;
bool operator<(const Punct &that)
{
if(x == that.x)
return y < that.y;
return x < that.x;
}
};
inline long long cp(const Punct &O, const Punct &A, const Punct &B)
{
return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (A.y - O.y) * (B.x - O.x);
}
//Daca e convex, orteaza v trigonometric
bool convex(vector<Punct> &v)
{
vector<bool> viz(v.size(), false);
vector<int> st(v.size());
int top = -1;
for(int i = 0, p = 1; i >= 0; i += p)
{
if(viz[i])
continue;
while(top >= 1 && cp(v[st[top-1]], v[st[top]], v[i]) < 0)
viz[st[top--]] = false;
st[++top] = i;
viz[i] = true;
if(i == v.size() - 1)
p = -1;
}
if(st.size() != v.size())
return false;
vector<Punct> t(st.size());
for(int i = 0; i < st.size(); ++i)
t[i] = v[st[i]];
v = t;
return true;
}
long long area(const vector<Punct> &v)
{
Punct O;
O.x = 0, O.y = 0;
long long ret = 0;
for(int i = 0; i < v.size()-1; ++i)
ret += cp(O, v[i], v[i+1]);
ret += cp(O, v.back(), v[0]);
return abs(ret);
}
int main()
{
ifstream in("gradina.in");
int n;
in >> n;
vector<Punct> v(n);
string rasp;
for(int i = 0; i < n; ++i)
{
in >> v[i].x >> v[i].y;
v[i].ind = i;
}
in.close();
long long difMin = (1LL << 62);
sort(v.begin(), v.end());
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
{
if(i == j)
continue;
vector<Punct> A, B;
for(int k = 0; k < n; ++k)
{
if(k == i)
{
A.push_back(v[k]);
continue;
}
if(k == j)
{
B.push_back(v[k]);
continue;
}
if((cp(v[i], v[j], v[k]) < 0) == (i > j))
A.push_back(v[k]);
else
B.push_back(v[k]);
}
if(A.size() <= 2 || B.size() <= 2)
continue;
if(convex(A) && convex(B))
{
long long dif = abs(area(A) - area(B));
if(dif <= difMin)
{
string s;
s.resize(n);
for(auto p:A)
s[p.ind] = 'V';
for(auto p:B)
s[p.ind] = 'I';
string t = s;
for(int i = 0; i < n; ++i)
t[i] = t[i] == 'V' ? 'S' : 'V';
if(t < s)
s = t;
if(dif < difMin)
rasp = s, difMin = dif;
else if(s < rasp)
rasp = s;
}
}
}
ofstream out("gradina.out");
out << difMin/2;
if(difMin % 2 == 0)
out << ".0";
else
out << ".5";
out << "\n";
out << rasp;
out.close();
return 0;
}