Pagini recente » Cod sursa (job #1349336) | Cod sursa (job #2218291) | Cod sursa (job #470424) | Cod sursa (job #1647816) | Cod sursa (job #3270986)
#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, l, r;
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;
}
ld 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 = {50000001, 50000001};
int pos = -1;
for(int i = 0; i < v.size(); i++) {
if(v[i].x < p0.x || (v[i].x == p0.x && v[i].y < p0.y)) {
p0 = v[i];
pos = i;
}
}
if(pos > 0)
swap(v[0], v[pos]);
sort(v.begin() + 1, v.end(), cmp);
bool ok = 0;
for(int i = 2; i < v.size(); i++) {
if(determ(v[i - 2], v[i - 1], v[i]) < 0) {
ok = 1;
break;
}
}
if(determ(v[v.size() - 2], v[v.size() - 1], v[0]) < 0 ||
determ(v[v.size() - 1], v[0], v[1]) < 0)
ok = 1;
return (!ok);
}
ld arie(vector <puncte> &v) {
ld 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 / 2.0;
}
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();
ld a1 = arie(st), a2 = arie(dr);
ld diff = fabs(a1 - a2);
if(diff <= ans) {
ans = diff;
string ion = "";
for(int i = 1; i <= st.size() + dr.size(); i++)
ion += 'V';
bool ok = 0; ///0 --> vasile, 1 --> ion
for(int i = 0; i < st.size(); i++) {
if(st[i].ind == 1) {
ok = 1;
break;
}
}
///FORMAM stringul
if(ok) { ///e in st
for(int i = 0; i < st.size(); i++)
ion[st[i].ind - 1] = 'I';
}
else {
for(int i = 0; i < st.size(); i++)
ion[dr[i].ind - 1] = 'I';
}
if(diff < ans) {
ans = diff;
ch = ion;
}
else if(diff == ans)
ch = min(ch, ion);
//cout << "CODEFORCES " << diff << " " << ion << '\n';
}
}
}
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";
}
for(int p1 = 1; p1 < n; p1++) {
for(int p2 = p1 + 1; p2 <= n; p2++) {
for(int i = 1; i <= n; i++) {
if(i == p1 || i == p2)
continue;
if(determ(a[p1], a[p2], a[i]) < 0)
l.push_back(a[i]);
else
r.push_back(a[i]);
}
//cout << "deci " << p1 << " " << p2 << '\n';
st = l, dr = r;
//cout << "test run ";
//print();
st.push_back(a[p1]), st.push_back(a[p2]);
check();
st = l;
st.push_back(a[p1]), dr.push_back(a[p2]);
check();
st = l, dr = r;
dr.push_back(a[p1]), st.push_back(a[p2]);
check();
st = l, dr = r;
dr.push_back(a[p1]), dr.push_back(a[p2]);
check();
st.clear(), dr.clear();
l.clear(), r.clear();
}
}
cout << ans << '\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]
*/