Cod sursa(job #1003217)

Utilizator andrettiAndretti Naiden andretti Data 29 septembrie 2013 22:34:11
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 255
#define inf 1LL<<60
using namespace std;

struct point{int x,y,ind;};
int n,n1,n2,u1,u2;
int h1[maxn],h2[maxn],v[maxn];
point p[maxn],p1[maxn],p2[maxn],ord;
long long sol=inf;
char s[maxn],aux[maxn];

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y),p[i].ind=i;
}

int side(point a,point b,point c)
{
    long long k=1LL*(c.x-a.x)*(b.y-a.y)-1LL*(c.y-a.y)*(b.x-a.x);
    if(k==0) return 0;
    else if(k>0) return 1;
    else return -1;
}

bool cmp(const point &a,const point &b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

void convex_hull(point pc[maxn],int &nc,int hc[maxn],int &uc)
{
    uc=2;
    hc[1]=1; hc[2]=2;
    for(int i=3;i<=nc;i++)
    {
        while(uc>1 && side(pc[hc[uc-1]],pc[hc[uc]],pc[i])>0) uc--;
        hc[++uc]=i;
    }
    memset(v,0,sizeof(v));
    for(int i=1;i<=uc;i++) v[hc[i]]=1;

    for(int i=nc;i>=1;i--)
    if(!v[i])
    {
        while(uc>1 && side(pc[hc[uc-1]],pc[hc[uc]],pc[i])>0) uc--;
        hc[++uc]=i;
    }
    hc[uc+1]=hc[1];
}

long long area(point pc[maxn],int hc[maxn],int uc)
{
    long long S=0;
    for(int i=1;i<=uc;i++)
     S+=(1LL*pc[hc[i]].x*pc[hc[i+1]].y-1LL*pc[hc[i+1]].x*pc[hc[i]].y);
    if(S<0) S=-S;
    return S;
}

void update()
{
    char ch1='I',ch2='V';
    if(u1+u2<n) return;

    for(int i=1;i<=u2;i++)
     if(p2[h2[i]].ind==1) {ch1='V'; ch2='I'; break;}

    for(int i=1;i<=u1;i++) aux[p1[h1[i]].ind]=ch1;
    for(int i=1;i<=u2;i++) aux[p2[h2[i]].ind]=ch2;

    long long newA=abs(area(p1,h1,u1)-area(p2,h2,u2));
    if(newA<sol || (newA==sol && strcmp(aux+1,s+1)<0))
    {
        sol=newA;
        memcpy(s,aux,sizeof(aux));
    }
}

void solve()
{
    sort(p+1,p+n+1,cmp);

    for(int i=1;i<n;i++)
     for(int j=i+1;j<=n;j++)
     {
         n1=n2=0;
         for(int k=1;k<=n;k++)
          if(k!=i && k!=j)
          {
             if(side(p[i],p[j],p[k])<0)
              p1[++n1]=p[k];
             else p2[++n2]=p[k];
          }
          else
           if(k==i) p1[++n1]=p[k];
           else p2[++n2]=p[k];

         if(n1<3 || n2<3) continue;
         convex_hull(p1,n1,h1,u1);
         convex_hull(p2,n2,h2,u2);
         update();
     }
}

void print()
{
    printf("%.1lf\n",(double)sol/2);
    for(int i=1;i<=n;i++) printf("%c",s[i]);
}

int main()
{
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);

    read();
    solve();
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}