Cod sursa(job #3359648)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 1 iulie 2026 16:10:07
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("gradina.in");
    ofstream fout("gradina.out");
#endif

typedef bitset<252> Config;
struct Punct {
    long long x, y;
} v[252];
struct Pilon {
    Punct p;
    long long i;
} cop[252];
long long n, i, j, k, mi;

Config rasp, ion;
long long top, stiv[252];
bool viz[252];

Punct stIon[252];
Punct stVas[252];
long long nrIon, nrVas;

static inline bool Cmp(Punct p1, Punct p2) {
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

static inline bool CmpPilon(Pilon p1, Pilon p2) {
    return Cmp(p1.p, p2.p);
}

static inline long long Det(Punct p1, Punct p2, Punct p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

static inline bool CmpConfig(const Config& a, const Config& b) {
    int i = n - 1;
    while(0 < i && a[i] == b[i]) i--;
    return a[i] < b[i];
}

static inline long long ArieConvexHull(Punct p[], int m) {
	if(3 > m) return 0;

	stiv[0] = 0;

	memset(viz, false, (m + 1) * sizeof(bool));
	stiv[top = 1] = 1;
	//viz[1] = 1;

	int sens = 1;

	for(int i = 2; i >= 1; i += sens) {
		if(viz[i]) continue;

		while(2 <= top && 0 > Det(p[i], p[stiv[top - 1]], p[stiv[top]])) {
            viz[stiv[top--]] = false;
		}

		stiv[++top] = i;
		viz[stiv[top]] = true;

		if(m == i) sens = -1;
	}

	if(m + 1 != top) return 0;

	long long arie = 0;
	for(int i = 1; i <= m; i++) {
		arie += p[stiv[i]].x * p[stiv[i + 1]].y - p[stiv[i]].y * p[stiv[i + 1]].x;
	}

	if(0 > arie) return -arie;
	return arie;
}

int main() {
    #if USE_STD_IO
        ios_base::sync_with_stdio(false);
    #endif // USE_STD_IO
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n;
    for(i = 1; i <= n; i++) {
        fin >> v[i].x >> v[i].y;
        cop[i].p = v[i];
        cop[i].i = i;
    }

    sort(v + 1, v + n + 1, Cmp);
    sort(cop + 1, cop + n + 1, CmpPilon);

    mi = INT_MAX;
    for(i = 1; i <= n; i++) {
        for(j = i + 1; j <= n; j++) {
            if(i == j) continue;

			ion = 0;
			nrIon = nrVas = 0;
			for(k = 1; k <= n; k++) {
				     if(k == i) stIon[++nrIon] = v[k], ion[k - 1] = true;
				else if(k == j) stVas[++nrVas] = v[k], ion[k - 1] = false;
				else if(0 > Det(v[k], v[i], v[j])) {
                    stIon[++nrIon] = v[k], ion[k - 1] = true;
				}
				else {
                    stVas[++nrVas] = v[k], ion[k - 1] = false;
				}
			}

			Config copIon = ion;
			for(k = 0; k < n; k++) {
				copIon[cop[k + 1].i - 1] = ion[k];
			}

			long long arie1 = ArieConvexHull(stIon, nrIon);
			long long arie2 = ArieConvexHull(stVas, nrVas);
			if(0 == arie2 || 0 == arie2) continue;

            int dif = arie1 - arie2;
			if(0 > dif) dif = -dif;

			if(dif < mi) {
                mi = dif;
                rasp = copIon;
			}
			else if(dif == mi && CmpConfig(copIon, rasp)) {
                rasp = copIon;
			}
        }
    }
    fout << mi / 2 << '.' << (1 & mi ? '5' : '0') << '\n';
    for(i = 0; i < n; i++) {
        fout << (rasp[i] ? 'I' : 'V');
    }

    return 0;
}