Cod sursa(job #2544173)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 11 februarie 2020 20:21:44
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <bits/stdc++.h>
using namespace std;

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

struct point{
    double x, y;
    int poz;
    bool operator<(point b){
        return x==b.x?y<b.y:x<b.x;
    }
    point operator- (point a){
        return {x-a.x, y-a.y};
    }
};

double cp(point o, point a, point b){
    a=a-o, b=b-o;
    return a.x*b.y-a.y*b.x;
}

double getarea(vector<point> v){
        double area=0;
        for(int i=1;i<v.size();++i){
            area+=cp({0, 0}, v[i-1], v[i]);
        }
        area+=cp({0, 0}, v[v.size()-1], v[0]);
        area=abs(area);
        area/=2;
        return area;
}

vector<point> hull(vector<point> v){
        vector<point> sol;
        for(int i=0,p=1;i>=0;i+=(p=i==(v.size()-1)?-p:p)){
            while(sol.size()>=2&&cp(sol[sol.size()-2], sol[sol.size()-1], v[i])<0) sol.pop_back();
            sol.push_back(v[i]);
        }
        sol.pop_back();
        return sol;
}

void show(vector<point> x){
    for(int i=0;i<x.size();++i){
        cout<<x[i].x<<" "<<x[i].y<<"\n";
    }
}

int main()
{
    int n;
    fin>>n;
    vector<point> x;
    for(int i=0;i<n;++i){
        point a;
        fin>>a.x>>a.y;
        a.poz=i;
        x.push_back(a);
    }
    double sol=(1<<30);
    string solcode;
    sort(x.begin(), x.end());
    for(int i=0;i<x.size();++i){
        for(int j=0;j<x.size();++j){
            if(j==i) continue;
            point a, b;
            a=x[i];
            b=x[j];
            vector<point> pa, pb;
            string s;
            s.resize(n);
            for(int k=0;k<x.size();++k){
                if(k==i) pa.push_back(a), s[x[k].poz]='I';
                else if(k==j) pb.push_back(b), s[x[k].poz]='V';
                else{
                    if(cp(a, b, x[k])>0) pa.push_back(x[k]), s[x[k].poz]='I';
                    else pb.push_back(x[k]), s[x[k].poz]='V';
                }
            }
            vector<point> hulla=hull(pa);
            vector<point> hullb=hull(pb);
            if(hulla.size()<pa.size()) continue;
            if(hullb.size()<pb.size()) continue;
            double dif=abs(getarea(hulla)-getarea(hullb));
            if(sol>dif){
                sol=dif;
                solcode=s;
            }
            else if(sol==dif){
                if(solcode>s) solcode=s;
            }
        }
    }
    fout<<fixed<<setprecision(10)<<sol<<"\n";
    fout<<solcode<<"\n";
    return 0;
}