Cod sursa(job #1659191)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 22 martie 2016 01:33:27
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define nmax 255
using namespace std;
struct point{int x;int y;int pos;};
int n;
double sol,soltrue=1<<30;
char ss[nmax],q[nmax];
point v[nmax];
point a[nmax],b[nmax];
point a1[nmax],b1[nmax];

int det(const point &a,const point &b,const point &c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmpsort(const point &a,const point &b)
{
    return det(v[1],a,b)>0;
}
void graham(point a[],point b[],int m,int &k)
{
    k=0;
    b[++k]=a[1];
    b[++k]=a[2];
    for (int i=3;i<=m;i++) {
        while (k>=2&&det(b[k-1],b[k],a[i])<0)
            k--;
        b[++k]=a[i];
    }
}
double arie(point a[],int m)
{
    a[m+1]=a[1];
    int d=0;
    for (int i=1;i<=m;i++)
        d+=det(a[0],a[i],a[i+1]);
    return abs(d)/2.0;
}

int main()
{
    int i,j=1,t;
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) {
        scanf("%d %d",&v[i].x,&v[i].y);
        v[i].pos=i;
        if (v[i].y<v[j].y||(v[i].y==v[j].y&&v[i].x<v[j].x))
            j=i;

    }
    swap(v[1],v[j]);
    sort(v+2,v+n+1,cmpsort);
    int m,m1,k,k1;

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) {
            m=k=0;
            for (t=1;t<=n;t++)
                if (t==i||det(v[i],v[j],v[t])>0)
                    a[++m]=v[t];
                else
                    b[++k]=v[t];
            if (m<3||k<3)
                continue;
            graham(a,a1,m,m1);
            graham(b,b1,k,k1);
            sol=abs(arie(a1,m1)-arie(b1,k1));
            if (sol<=soltrue) {
                for (i=1;i<=m;i++)
                    q[a[i].pos-1]='I';
                for (i=1;i<=k;i++)
                    q[b[i].pos-1]='V';
                if (q[0]=='V')
                    for (i=0;i<n;i++)
                        q[i]='I'+'V'-q[i];
                if (sol<soltrue||(sol==soltrue&&strcmp(q,ss)==0)) {
                    soltrue=sol;
                    strcpy(ss,q);
                }
            }
        }
    printf("%.1lf\n%s\n",soltrue,ss);
    return 0;
}