Pagini recente » Cod sursa (job #300271) | Cod sursa (job #1456208) | Cod sursa (job #1264021) | Cod sursa (job #1499644) | Cod sursa (job #3271218)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
const int NMAX = 252;
using ld = long double;
using ll = long long;
ifstream cin("gradina.in");
ofstream cout("gradina.out");
struct puncte {
ll x, y;
int ind;
}a[NMAX];
vector <puncte> st, dr;
ll determ(puncte a, puncte b, puncte c) {
return a.x * b.y + b.x * c.y + c.x * a.y -
a.y * b.x - b.y * c.x - c.y * a.x;
}
ll ans = 1e18;
string ch;
puncte p0;
bool cmp(puncte a, puncte b) { ///panta inmultita
return (b.x - p0.x) * (a.y - p0.y) < (a.x - p0.x) * (b.y - p0.y);
}
bool infasuratoare(vector <puncte> &v) {
p0 = v[0]; ///asa ar trebui, ca deja sunt sortate
sort(v.begin() + 1, v.end(), cmp);
for(int i = 2; i < v.size(); i++) {
if(determ(v[i - 2], v[i - 1], v[i]) < 0)
return false;
}
if(determ(v[v.size() - 2], v[v.size() - 1], v[0]) < 0 ||
determ(v[v.size() - 1], v[0], v[1]) < 0)
return false;
return true;
}
ll arie(vector <puncte> &v) { ///LA FINAL /2
ll sum = 0;
for(int i = 0; i + 1 < v.size(); i++)
sum += (v[i].x * v[i + 1].y - v[i + 1].x * v[i].y);
sum += (v[v.size() - 1].x * v[0].y - v[0].x * v[v.size() - 1].y);
return sum;
}
void print() {
cout << "yoo\n";
for(int i = 0; i < st.size(); i++)
cout << st[i].ind << " ";
cout << '\n';
for(int i = 0; i < dr.size(); i++)
cout << dr[i].ind << " ";
cout << '\n';
}
void check() { ///cu st si dr
if(st.size() < 3 || dr.size() < 3) ///n-ai csf
return;
if(infasuratoare(st) && infasuratoare(dr)) {
//print();
ll a1 = arie(st), a2 = arie(dr);
ll diff = abs(a1 - a2);
if(diff <= ans) {
string ion = "";
ion.resize(st.size() + dr.size());
for(int i = 0; i < st.size(); i++)
ion[st[i].ind - 1] = 'I';
for(int i = 0; i < dr.size(); i++)
ion[dr[i].ind - 1] = 'V';
if(ion[0] == 'V') {
for(int i = 0; i < ion.size(); i++) {
if(ion[i] == 'V')
ion[i] = 'I';
else
ion[i] = 'V';
}
}
if(diff < ans || (ans == diff && ion < ch)) {
//cout << diff << " " << ion << '\n';
ans = diff;
ch = ion;
}
//cout << "CODEFORCES " << diff << " " << ion << '\n';
}
}
}
bool cmpdir(puncte a, puncte b) {
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
a[i].ind = i;
ch += 'V';
}
sort(a + 1, a + n + 1, cmpdir);
for(int p1 = 1; p1 <= n; p1++) {
for(int p2 = 1; p2 <= n; p2++) {
if(p1 == p2)
continue;
for(int i = 1; i <= n; i++) {
if(i == p1 || determ(a[p1], a[p2], a[i]) < 0)
st.push_back(a[i]);
else
dr.push_back(a[i]);
}
//cout << "deci " << p1 << " " << p2 << '\n';
//cout << "test run ";
//print();
check();
st.clear(), dr.clear();
}
}
cout << setprecision(1) << fixed << (ld)ans / 2.0 << '\n' << ch;
return 0;
}
/*
- iei cate 2 puncte si le imparti pe celelalte in functie de
partea dreptei pe care sunt
- pt ambele 2 multimi de planuri, faci infasuratoare, DAR
iei cele 2 puncte ce formeaza dreapta in fiecare in parte,
ca sa incerci (si unul cu unul, si impreuna)
- dc MERG ambele infasuratori si includ TOTI tarusii, compari aria
- cum stii care-i Ion? In functie de care parte include v[1]
*/