Cod sursa(job #2339470)

Utilizator DavidLDavid Lauran DavidL Data 8 februarie 2019 22:35:09
Problema Gradina Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 13.73 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fi("gradina.in");
ofstream fo("gradina.out");

const int NMAX = 300;

struct punct
{
    int x, y;
};

struct punctS
{
    punct M;
    int poz;
};

bool operator <(const punct &a, const punct &b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

bool operator <(const punctS &a, const punctS &b)
{
    return a.M < b.M;
}

punctS P[NMAX];
punct sus[NMAX], jos[NMAX];
int cntSus, cntJos;
int n;
punct stivaSus[NMAX], stivaJos[NMAX];
int kSus, kJos;
bool afara;

int verifica(punct A, punct B, punct C)
{
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y) ;
}

long double dist(punct A, punct B)
{
    return (long double)sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

long double unghi(punct A, punct B)
{
    if (A.x <= B.x && A.y <= B.y) // cadranul 1
    {
        return 2 + 1.00 * (B.y - A.y) / dist(A, B);
    }
    else if (A.x >= B.x && A.y <= B.y) // cadranul 2
    {
        return 3 + 1.00 * (A.x - B.x) / dist(A, B);
    }
    else if (A.x >= B.x && A.y >= B.y) // cadranul 3
    {
        return 1.00 * (A.y - B.y) / dist(A, B);
    }
    else // cadranul 4
    {
        return 1 + 1.00 * (B.x - A.x) / dist(A, B);
    }
}

long double faTot(punct A[NMAX], int n) // returneaza aria
{
    if (n == 2)
        return 0;

    kJos = 0;
    kSus = 0;

    long double dr = unghi(A[1], A[n]);
    stivaSus[++kSus] = A[1];
    stivaJos[++kJos] = A[1];

    for (int i = 2; i <= n; i++)
    {
        if (unghi(A[1], A[i]) > dr || i == n) // sus
        {
            while (kSus >= 2 && unghi(stivaSus[kSus - 1], stivaSus[kSus]) < unghi(stivaSus[kSus - 1], A[i]))
                kSus--, afara = 1;
            stivaSus[++kSus] = A[i];
        }
        if (unghi(A[1], A[i]) < dr || i == n) // jos
        {
            while (kJos >= 2 && unghi(stivaJos[kJos - 1], stivaJos[kJos]) > unghi(stivaJos[kJos - 1], A[i]))
                kJos--, afara = 1;
            stivaJos[++kJos] = A[i];
        }
    }

    //for (int i = 1; i <= kJos; i++)
        //cout << stivaJos[i].x << " " << stivaJos[i].y << "\n";

    vector <punct> poligon;
    for (int i = 1; i <= kSus; i++)
        poligon.push_back(stivaSus[i]);
    for (int i = kJos - 1; i >= 1; i--)
        poligon.push_back(stivaJos[i]);

    long double ret = 0;
    for (int i = 1; i < poligon.size(); i++)
    {
        ret += (poligon[i - 1].x * poligon[i].y - poligon[i].x * poligon[i - 1].y);
    }
    ret = ret / 2.00;
    return abs(ret);
}

signed main()
{
    fi >> n;
    for (int i = 1; i <= n; i++)
    {
        fi >> P[i].M.x >> P[i].M.y, P[i].poz = i;
        P[i].M.x += 50000000;
        P[i].M.y += 50000000;
    }

    sort(P + 1, P + n + 1);

    long double minim = 2000000000;
    string configOptim = "";
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;

            // i la ion, j la domnu vasile
            punct baza, varf; // baza=punctul care e mai in stanga
            if (P[j] < P[i])
                baza = P[j].M, varf = P[i].M;
            else
                baza = P[i].M, varf = P[j].M;

            cntSus = cntJos = 0;
            // sus punem J, jos punem I
            string config = "";
            config.resize(n);

            for (int k = 1; k <= n; k++)
            {
                if ((verifica(baza, varf, P[k].M) > 0 && k != i) || k == j) // e sus, la Vasile
                {
                    sus[++cntSus] = P[k].M;
                    config[P[k].poz - 1] = 'V';
                }
                else
                {
                    jos[++cntJos] = P[k].M;
                    config[P[k].poz - 1] = 'I';
                }
            }

            afara = 0;
            long double a1 = faTot(sus, cntSus);
            if (afara)
                continue;

            afara = 0;
            long double a2 = faTot(jos, cntJos);
            if (afara)
                continue;

            //for (int i = 1; i <= cntJos; i++)
                //cout << jos[i].x << ", " << jos[i].y << "\n";
            string opus = "";
            for (auto pp: config)
                opus += (pp == 'I' ? 'V' : 'I');

            if (abs(a2 - a1) < minim || (abs(a2 - a1) == minim && (config < configOptim || opus < configOptim)))
            {
                minim = abs(a2 - a1);
                configOptim = min(config, opus);
            }
        }
    }
    fo << fixed << setprecision(1) << minim << "\n" << configOptim;

    return 0;
}









/*
#include <cstdio>
#include <algorithm>
using namespace std;
struct Points
{
    int x,y,ind;
};
Points v[255];
Points s1[255];
Points s2[255];
Points p1[255];
Points p2[255];
bool sol[255];
bool ans[255];
bool cmp1(Points P1, Points P2)
{
    if(P1.x==P2.x)
        return P1.y<P2.y;
    return P1.x<P2.x;
}
bool cmp2(Points P1, Points P2)
{
    if(P1.x==P2.x)
        return P1.y>P2.y;
    return P1.x<P2.x;
}
long long det(Points P1, Points P2, Points P3)
{
    return (P2.x-P1.x)*1LL*(P3.y-P1.y)-(P2.y-P1.y)*1LL*(P3.x-P1.x);
}
long long arie(Points a[], int n)
{
    long long ar=0;
    Points LL;
    LL.x=LL.y=0;
    int i;
    for(i=2; i<=n; i++)
        ar+=det(LL, a[i-1], a[i]);
    ar+=det(LL, a[n], a[1]);
    return ar;
}
int main()
{   freopen("gradina.in", "r",stdin);
    freopen("gradina.out", "w",stdout);
    int n,i,j,k,top1,top2,ok,n1,n2;
    long long ar1,ar2,minn=1000000000000000000;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d", &v[i].x, &v[i].y);
        v[i].ind=i;
        s1[i]=v[i];
        s2[i]=v[i];
    }
    sort(s1+1, s1+n+1,cmp1);
    sort(s2+1, s2+n+1,cmp2);
    for(i=1; i<=n; i++){
        for(j=i+1; j<=n; j++){
            top1=top2=0;
            ok=0;
            for(k=1; k<=n; k++){
                if(det(v[i], v[j], s1[k])>0){
                    while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
                        top1--;
                    p1[++top1]=s1[k];
                }
                else{
                    if(det(v[i], v[j], s1[k])==0){
                        if(ok==1){
                            while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
                                top2--;
                            p2[++top2]=s1[k];
                        }
                        else{
                            while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
                                top1--;
                            p1[++top1]=s1[k];
                            ok=1;
                        }
                    }
                    else{
                        while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
                            top2--;
                        p2[++top2]=s1[k];
                    }
                }
            }
            n1=top1;
            n2=top2;
            ok=0;
            for(k=1; k<=n; k++){
                if(det(v[i], v[j], s2[k])>0){
                    while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
                        top1--;
                    p1[++top1]=s2[k];
                }
                else{
                    if(det(v[i], v[j], s2[k])==0){
                        if(ok==1){
                            while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
                                top2--;
                            p2[++top2]=s2[k];
                        }
                        else{
                            while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
                                top1--;
                            p1[++top1]=s2[k];
                            ok=1;
                        }
                    }
                    else{
                        while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
                            top2--;
                        p2[++top2]=s2[k];
                    }
                }
            }
            if(p1[top1].x==p1[top1-1].x)
                top1-=2;
            else
                top1--;
            reverse(p1+n1+1, p1+top1+1);
            if(p1[1].ind==p1[top1].ind)
                top1--;
            if(p2[top2].x==p2[top2-1].x)
                top2-=2;
            else
                top2--;
            reverse(p2+n2+1, p2+top2+1);
            if(p2[1].ind==p2[top2].ind)
                top2--;
            if(top1+top2==n){
                ar1=arie(p1, top1);
                ar2=arie(p2, top2);
                ok=0;
                if(abs(ar1-ar2)<minn){
                    minn=abs(ar1-ar2);
                    for(k=1; k<=top1; k++)
                        ans[p1[k].ind]=0;
                    for(k=1; k<=top2; k++)
                        ans[p2[k].ind]=1;
                    if(ans[1]==1)
                        ok=1;
                    for(k=1; k<=n; k++)
                        sol[k]=(ans[k]+ok)%2;
                }
                else
                    if(abs(ar1-ar2)==minn){
                        for(k=1; k<=n && sol[k]==(ans[k]+ok)%2; k++);
                            if(sol[k]>(ans[k]+ok)%2)
                                for(; k<=n; k++)
                                    sol[k]=(ans[k]+ok)%2;
                    }
            }
            top1=top2=0;
            ok=1;
            for(k=1; k<=n; k++){
                if(det(v[i], v[j], s1[k])>0){
                    while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
                        top1--;
                    p1[++top1]=s1[k];
                }
                else{
                    if(det(v[i], v[j], s1[k])==0){
                        if(ok==1){
                            while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
                                top2--;
                            p2[++top2]=s1[k];
                            ok=0;
                        }
                        else{
                            while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
                                top1--;
                            p1[++top1]=s1[k];
                        }
                    }
                    else{
                        while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
                            top2--;
                        p2[++top2]=s1[k];
                    }
                }
            }
            n1=top1;
            n2=top2;
            ok=1;
            for(k=1; k<=n; k++){
                if(det(v[i], v[j], s2[k])>0){
                    while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
                        top1--;
                    p1[++top1]=s2[k];
                }
                else{
                    if(det(v[i], v[j], s2[k])==0){
                        if(ok==1){
                            while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
                                top2--;
                            p2[++top2]=s2[k];
                            ok=0;
                        }
                        else{
                            while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
                                top1--;
                            p1[++top1]=s2[k];
                        }
                    }
                    else{
                        while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
                            top2--;
                        p2[++top2]=s2[k];
                    }
                }
            }
            if(p1[top1].x==p1[top1-1].x)
                top1-=2;
            else
                top1--;
            reverse(p1+n1+1, p1+top1+1);
            if(p1[1].ind==p1[top1].ind)
                top1--;
            if(p2[top2].x==p2[top2-1].x)
                top2-=2;
            else
                top2--;
            reverse(p2+n2+1, p2+top2+1);
            if(p2[1].ind==p2[top2].ind)
                top2--;
            if(top1+top2==n){
                ar1=arie(p1, top1);
                ar2=arie(p2, top2);
                ok=0;
                if(abs(ar1-ar2)<minn){
                    minn=abs(ar1-ar2);
                    for(k=1; k<=top1; k++)
                        ans[p1[k].ind]=0;
                    for(k=1; k<=top2; k++)
                        ans[p2[k].ind]=1;
                    if(ans[1]==1)
                        ok=1;
                    for(k=1; k<=n; k++)
                            sol[k]=(ans[k]+ok)%2;
                }
                else
                    if(abs(ar1-ar2)==minn){
                        for(k=1; k<=n && sol[k]==(ans[k]+ok)%2; k++);
                            if(sol[k]>(ans[k]+ok)%2)
                                for(; k<=n; k++)
                                    sol[k]=(ans[k]+ok)%2;
                    }
            }
        }
    }
    if(minn%2==0)
        printf("%lld.0\n", minn/2);
    else
        printf("%lld.5\n", minn/2);
    for(i=1; i<=n; i++){
        if(sol[i]==0)
            printf("I");
        else
            printf("V");
    }
    return 0;
}
*/












/*
#include <bits/stdc++.h>
using namespace std;
ofstream fo("gradina.in");

int main()
{
    srand(time(NULL));
    int n = rand() % 5 + 5;
    fo << n << "\n";
    for (int i = 1; i <= n; i++)
    {
        int x = (rand() % 10);
        int semn = rand() % 2;
        if (semn == 0)
            x = -x;
        int y = (rand() % 10);
        semn = rand() % 2;
        if (semn == 0)
            y = -y;
        fo << x << " " << y << "\n";
    }

    return 0;
}*/