Cod sursa(job #3248263)

Utilizator Tud00rCristea Tudor Tud00r Data 11 octombrie 2024 12:56:29
Problema Gradina Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream fin("gradina.in");
ofstream fout("gradina.out");

struct pct{
    double x,y;
    int semiplan,ordine;
}v[251],sir1[251],sir2[251];

int n,sol[251];
double minim=10000000000;

int compara(pct a, pct b){
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

double arie(pct a, pct b, pct 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 inf_conv(pct w[],int n){
    for(int i=2;i<n;i++){
        if(arie(w[1],w[n],w[i])<0)
            w[i].semiplan=1;
        else
            w[i].semiplan=2;
    }
    int k=1, stiva[251],ck;
    stiva[1]=1;
    for(int i=2;i<=n;i++)
        if(w[i].semiplan==1 || w[i].semiplan==0){
            while(k>1&&arie(w[stiva[k-1]],w[stiva[k]],w[i])<0)
                k--;
            stiva[++k]=i;
        }
    ck=k;
    stiva[k]=n;
    for(int i=n-1;i>=1;i--)
        if(w[i].semiplan==2||w[i].semiplan==0){
            while(k>ck&&arie(w[stiva[k-1]],w[stiva[k]],w[i])<0)
                k--;
            stiva[++k]=i;
        }
    double suma=0;
    for(int i=2;i<k-1;i++)
        suma+=abs(arie(w[1],w[stiva[i]],w[stiva[i+1]]))/2.0;
    return suma;
}

void dif_arii(int n){
    int n1=0,n2=0,stop=1;
    double ar1=0,ar2=0;
    for(int i=1;i<=n;i++){
        if(v[i].semiplan==1)
            sir1[++n1]=v[i];
        else
            sir2[++n2]=v[i];
    }
    ar1=inf_conv(sir1,n1);
    ar2=inf_conv(sir2,n2);
    if(abs(ar1-ar2)==minim){
        int sol2[251];
        for(int i=1;i<=n;i++){
            sol2[v[i].ordine] = v[i].semiplan;
        }
        for(int i=1;i<=n;i++){
            if(sol[i]>sol2[i])
                stop=0;
        }
        if(stop==0)
            for(int i=1;i<=n;i++)
                sol[i]=sol2[i];
    }
    if (abs(ar1-ar2)<minim) {
        minim=abs(ar1-ar2);
        for (int i=1;i<=n;i++)
            sol[v[i].ordine]=v[i].semiplan;

    }
}

int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        v[i].ordine=i;
    }
    sort(v+1,v+n+1,compara);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            for(int q=1;q<=n;q++)
                if(q!=i&&q!=j){
                    if(arie(v[i],v[j],v[q])<0)
                        v[q].semiplan=1;
                    else
                        v[q].semiplan=2;
                }
                v[i].semiplan=1;
                v[j].semiplan=2;
                dif_arii(n);
                v[i].semiplan=2;
                v[j].semiplan=1;
                dif_arii(n);
        }
    fout<<fixed<<setprecision(1)<<minim<<endl;
    for(int i=1;i<=n;i++){
        if(sol[i]==sol[1])
            fout<<"I";
        else
            fout<<"V";
    }
    return 0;
}