Cod sursa(job #2965612)

Utilizator Andrei_ierdnANeculau Rares-Andrei Andrei_ierdnA Data 15 ianuarie 2023 17:12:07
Problema Gradina Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.75 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream f("gradina.in");
ofstream g("gradina.out");

const long long CCW = -1, COL = 0, CW = 1;
#define MAX 50000000LL

long long n, i, j, k, nr1, nr2, aux, mindif = 4000000000000000000LL, whohas[252], ok;
long long area1, area2;
long long lowerHull[252], upperHull[252], lowerN, upperN;
char solconfig[252], newconfig[252];

struct Punct
{
    long long x, y, i;
}
tarusi[252], tarusi1[252], tarusi2[252];

struct Dreapta
{
    long long a, b, c;
}
limdr;

bool operator < (const Punct &a, const Punct &b)
{
    if (a.x < b.x)
        return true;
    else if (a.x == b.x) {
        if (a.y < b.y)
            return true;
    }
    return false;
}

Dreapta createLine(const Punct &p1, const Punct &p2)
{
    Dreapta aux;
    aux.a = p1.y - p2.y;
    aux.b = p2.x - p1.x;
    aux.c = -(aux.a * p1.x + aux.b * p1.y);
    return aux;
}

long long getOrientation(const Punct &a, const Punct &b, const Punct &c)
{
    long long crossProduct = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
    if (crossProduct == 0)
        return COL;
    if (crossProduct > 0)
        return CCW;
    return CW;
}

inline long long getTrapezoidArea(const Punct &a, const Punct &b)
{
    return (b.x - a.x) * (a.y + b.y + 2*MAX);
}

long long getConvexHullArea(Punct *pcts, long long n)
{
    long long i = 0;
    lowerHull[++lowerN] = 1;
    lowerHull[++lowerN] = 2;
    for (i = 3; i <= n; i++) {
        while (lowerN >= 2 && getOrientation(pcts[lowerHull[lowerN-1]], pcts[lowerHull[lowerN]], pcts[i]) == CW)
            lowerN--;
        lowerHull[++lowerN] = i;
    }
    upperHull[++upperN] = n;
    upperHull[++upperN] = n-1;
    for (i = n-2; i >= 1; i--) {
        while (upperN >= 2 && getOrientation(pcts[upperHull[upperN-1]], pcts[upperHull[upperN]], pcts[i]) == CW)
            upperN--;
        upperHull[++upperN] = i;
    }
    lowerN--;
    upperN--;
    if (lowerN + upperN == n) {
        for (i = 1; i <= upperN; i++)
            lowerHull[lowerN+i] = upperHull[i];
        lowerHull[lowerN+upperN+1] = lowerHull[1];
        upperN = 0;
        lowerN = 0;
        long long area = 0.0;
        for (long long i = 1; i <= n; i++) {
            area = area + getTrapezoidArea(pcts[lowerHull[i]], pcts[lowerHull[i+1]]);
        }
        return area;
    }
    return 0;
}

int main()
{
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> tarusi[i].x >> tarusi[i].y;
        tarusi[i].i = i;
    }
    sort(tarusi+1, tarusi+n+1);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j)
                continue;
            nr1 = 0;
            nr2 = 0;
            for (k = 1; k <= n; k++) {
                aux = getOrientation(tarusi[i], tarusi[j], tarusi[k]);
                if (aux == COL || aux == CCW) {
                    tarusi1[++nr1] = tarusi[k];
                    whohas[tarusi[k].i] = 0;
                }
                else {
                    tarusi2[++nr2] = tarusi[k];
                    whohas[tarusi[k].i] = 1;
                }
            }
            if (nr1 >= 3 && nr2 >= 3) {
                area1 = abs(getConvexHullArea(tarusi1, nr1));
                area2 = abs(getConvexHullArea(tarusi2, nr2));
                if (!area1 || !area2)
                    continue;
                if (whohas[1] == 0) {
                    for (k = 1; k <= n; k++)
                        newconfig[k] = (whohas[k] == 0) ? 'I' : 'V';
                }
                else {
                    for (k = 1; k <= n; k++)
                        newconfig[k] = (whohas[k] == 0) ? 'V' : 'I';
                }
                if (abs(area1-area2) < mindif) {
                    mindif = abs(area1-area2);
                    for (k = 1; k <= n; k++)
                        solconfig[k] = newconfig[k];
                }
                else if (abs(area1-area2) == mindif) {
                    ok = 0;
                    for (k = 1; k <= n; k++) {
                        if (newconfig[k] < solconfig[k]) {
                            ok = 1;
                            k = n+1;
                        }
                        else if (newconfig[k] > solconfig[k]) {
                            k = n+1;
                        }
                    }
                    if (ok == 1) {
                        for (k = 1; k <= n; k++)
                            solconfig[k] = newconfig[k];
                    }
                }
            }
        }
    }
    g << std::fixed << setprecision(1);
    g << ((long double)mindif) / 2.0;
    g << '\n';
    g << (solconfig+1);
    f.close();
    g.close();
    return 0;
}