Cod sursa(job #1664265)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 26 martie 2016 12:31:42
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 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,semn;
double sol,soltrue=1<<30;
char ss[nmax],q[nmax];
point v[nmax],aux;
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(aux,a,b)>0;
}
int convex(point a[],int m)
{
    if (m==2)
        return 1;
    semn=det(a[m-1],a[m],a[1])<0;

    if ((det(a[m],a[1],a[2])<0)!=semn)
        return 0;
    for (int i=3;i<=m;i++)
        if ((det(a[i-2],a[i-1],a[i])<0)!=semn)
            return 0;
    return 1;
}
void graham(point a[],point b[],int m,int &k)
{
    int i,j=1;
    k=0;
    for (i=1;i<=m;i++)
        if (a[i].y<a[j].y||(a[i].y==a[j].y&&a[i].x<a[j].x))
            j=i;
    swap(a[1],a[j]);
    aux=a[1];
    sort(a+2,a+m+1,cmpsort);
    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];
    }
    if (!convex(b,k)) {
        m=0;
        return;
    }

}
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;
    }
    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) {
                    a[++m]=v[t];
                    continue;
                }
                if (t==j) {
                    b[++k]=v[t];
                    continue;
                }
                if (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);

            if (m1==0&&k1==0)
                continue;

            sol=abs(arie(a1,m1)-arie(b1,k1));

            if (sol<=soltrue) {
                for (t=1;t<=m;t++)
                    q[a[t].pos-1]='I';
                for (t=1;t<=k;t++)
                    q[b[t].pos-1]='V';
                if (q[0]=='V')
                    for (t=0;t<n;t++)
                        q[t]='I'+'V'-q[t];
                if (sol<soltrue||(sol==soltrue&&strcmp(q,ss)==0)) {
                    soltrue=sol;
                    strcpy(ss,q);
                }
            }
        }
    printf("%.1lf\n%s\n",soltrue,ss);

    return 0;
}