Cod sursa(job #1259462)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 10 noiembrie 2014 00:11:47
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.63 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>

#define lint long long int
#define inf 12100000000000005ll
using namespace std;

struct point{
    int x,y;
    int poz;

    point(int x=0,int y=0, int poz=0): x(x), y(y), poz(poz) {}
};

lint ccw(const point &a,const point &b,const point &c){
    return ((a.x-b.x+0ll)*(c.y-b.y)-(a.y-b.y+0ll)*(c.x-b.x));
}

//point centru;
bool operator<(const point &a,const point &b){
    //return ccw(a,centru,b)>0;
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

bool prost;
vector<point> convex_hull(vector<point> &points){
    if(points.size()<=2)
        return points;

    int n=points.size();//,poz=0;

    /*for(int i=0;i<n;i++)
        if(points[i].x<points[poz].x || (points[i].x==points[poz].x && points[i].y<points[poz].y))
            poz=i;

    swap(points[poz],points[0]);
    centru=points[0];

    sort(points.begin()+1,points.end());*/

    vector<point> ans;
    ans.push_back(points[0]);
    ans.push_back(points[1]);

    for(int i=2;i<n;i++){
        while(ans.size()>1)
            if(ccw(ans[ans.size()-2],ans.back(),points[i])>0)
                ans.pop_back();
            else
                break;

        ans.push_back(points[i]);
    }

    int sz=ans.size()-1;
    ans.push_back(points[n-2]);

    for(int i=n-3;i>=0;i--){
        while(ans.size()+sz>1)
            if(ccw(ans[ans.size()-2],ans.back(),points[i])>0)
                ans.pop_back();
            else
                break;

        ans.push_back(points[i]);
    }

    ans.pop_back();

    if(ans.size()!=points.size())
        prost=true;

    return ans;
}

lint arie(vector<point> &points){
    lint ans=0;

    for(int i=1;i+1<points.size();i++)
        ans+=ccw(points[0],points[i],points[i+1]);

    return ans;
}

point v[260];
char sir[260];
char rasp[260];

int perm[260];

int main()
{
    ifstream cin("gradina.in");
    ofstream cout("gradina.out");

    int n=0,i,j,k;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        v[i].poz=i;
    }

    vector<point> ion,vasile;

    lint ans=inf;

    sort(v+1,v+n+1);
    for(i=1;i<=n;i++)
        perm[v[i].poz]=i;

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j){
                sir[i]='I';
                sir[j]='V';

                for(k=1;k<=n;k++)
                    if(k!=i && k!=j){
                        if(ccw(v[i],v[j],v[k])>0)
                            sir[k]='I';
                        else
                            sir[k]='V';
                    }

                ion.clear();vasile.clear();
                for(k=1;k<=n;k++)
                    if(sir[k]=='I')
                        ion.push_back(v[k]);
                    else
                        vasile.push_back(v[k]);

                prost=false;

                vasile=convex_hull(vasile);
                ion=convex_hull(ion);

                if(prost)
                   continue;

                lint a=arie(ion);
                lint b=arie(vasile);

                if(abs(a-b)<ans){
                    if(sir[perm[1]]=='V'){
                        for(k=1;k<=n;k++)
                            if(sir[k]=='V')
                                sir[k]='I';
                            else
                                sir[k]='V';
                    }

                    ans=abs(a-b);
                    for(k=1;k<=n;k++)
                        rasp[k]=sir[k];
                }
                else if(abs(a-b)==ans){
                    if(sir[perm[1]]=='V'){
                        for(k=1;k<=n;k++)
                            if(sir[k]=='V')
                                sir[k]='I';
                            else
                                sir[k]='V';
                    }

                    prost=false;
                    for(k=1;k<=n;k++)
                        if(rasp[perm[k]]==sir[perm[k]])
                            rasp[perm[k]]=sir[perm[k]];
                        else if(rasp[perm[k]]<sir[perm[k]]){
                            prost=true;
                            break;
                        }
                        else
                            break;

                    if(prost)
                        continue;

                    for(;k<=n;k++)
                        rasp[perm[k]]=sir[perm[k]];
                }
            }

    cout<<fixed<<setprecision(1)<<ans/2.0<<'\n';
    for(i=1;i<=n;i++)
        cout<<rasp[perm[i]];

    cin.close();
    cout.close();
    return 0;
}