Cod sursa(job #3247052)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 5 octombrie 2024 13:08:55
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct{
    int x, y, tip, ord;
}puncte[255], s1[255], s2[255];

int sol[255];

double minn = 1e9;

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

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

double infasuratoare_convexa(punct v[], int n) {
    
    int t[255], st[255];
    
    for (int i = 2; i < n; i++) {
        if (arie(v[1], v[n], v[i]) < 0)
        
            t[i] = 1;
        else
            t[i] = 2;
    }
    
    t[1] = t[n] = 0;
    
    int k = 1;
    st[1] = 1;
    
    for (int i = 2; i <= n; i++)
        if (t[i] == 1 || t[i] == 0) {
            
            while (k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                return -1;
            k++;
            st[k] = i;
            
        }
        
    int ck = k;
    
    for (int i = n - 1; i >= 1; i--)
        if (t[i] == 2 || t[i] == 0) {
            
            while (k > ck && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                return -1;
                
            k++;
            st[k] = i;
            
        }
        
    k--;
    
    double s = 0;
    
    for (int i = 2; i < k; i++)
    
        s += abs(arie(v[1], v[st[i]], v[st[i + 1]])) / 2.0;
        
    return s;
}

void diferenta(int n) {
    
    int cnt1 = 0, cnt2 = 0;
    
    for (int i = 1; i <= n; i++)
        if (puncte[i].tip == 1)
        
            s1[++cnt1] = puncte[i];
        else
        
            s2[++cnt2] = puncte[i];

    if (cnt1 < 3 || cnt2 < 3)
        return;
        
    double sum1 = infasuratoare_convexa(s1, cnt1);
    double sum2 = infasuratoare_convexa(s2, cnt2);
    
    if (sum1 < 0 || sum2 < 0)
        return;
        
    if(abs(sum1 - sum2) == minn) {
        
        int csol[n + 1];
        for (int i = 1; i <= n; i++)
            csol[i] = sol[i];
            
        for (int i = 1; i <= n; i++) {
            
            if (csol[i] > puncte[i].tip)
                break;
                
            if (csol[i] == puncte[i].tip)
                continue;
                
            if (csol[i] < puncte[i].tip)
                return;
                
        }
        
        for (int i = 1; i <= n; i++)
            sol[i] = csol[i];
            
    }
    
    if (abs(sum1 - sum2) < minn) {
        
        minn = abs(sum1 - sum2);
        
        for (int i = 1; i <= n; i++)
            sol[puncte[i].ord] = puncte[i].tip;
            
    }
}

int main()
{
    int n;
    f >> n;
    
    for (int i = 1;i <= n; i++) {
        
        f >> puncte[i].x >>puncte[i].y;
        
        puncte[i].ord = i;
        
    }
    
    sort(puncte + 1, puncte + n + 1, cmp);
    
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) {
            
            for (int k = 1; k <= n; k++)
            
                if (k != i && k != j) {
                    if (arie(puncte[i], puncte[j], puncte[k]) < 0)
                        puncte[k].tip = 1;
                    else
                        puncte[k].tip = 2;
                }
                
            puncte[i].tip = 1;
            puncte[j].tip = 2;
            
            diferenta(n);
            
            puncte[i].tip = 2;
            puncte[j].tip = 1;
            
            diferenta(n);
        }
        
    g << fixed << setprecision(1) << minn << "\n";
    
    for (int i = 1; i <= n; i++)
    
        if (sol[i] == sol[1])
            g << 'I';
        else
            g << 'V';
            
    return 0;
}