Cod sursa(job #1003157)

Utilizator andrettiAndretti Naiden andretti Data 29 septembrie 2013 20:44:03
Problema Gradina Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 255
#define inf 0x3f3f3f3f
using namespace std;

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

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)
{
    double k=(double)(c.x-a.x)*(b.y-a.y)-(double)(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){
    return side(ord,a,b)<0;
}

void convex_hull(point pc[maxn],int &nc,int hc[maxn],int &uc)
{
    int minx=inf,miny=inf,pos;
    for(int i=1;i<=nc;i++)
     if(pc[i].y<miny || (pc[i].y==miny && pc[i].x<minx)){
         miny=p[i].y; minx=p[i].x; pos=i;
     }
    swap(pc[1],pc[pos]); ord=pc[1];
    sort(pc+2,pc+nc+1,cmp);

    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;
    }
    hc[uc+1]=hc[1];
}

double 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 (double)S/2;
}

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;

    double newA=fabs(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()
{
    for(int i=1;i<n;i++)
     for(int j=i+1;j<=n;j++)
     {
         n1=n2=0;
         p1[++n1]=p[i]; p2[++n2]=p[j];
         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];
          }
         if(n1<3 || n2<3) continue;
         convex_hull(p1,n1,h1,u1);
         convex_hull(p2,n2,h2,u2);
         update();
     }
}

void print()
{
    printf("%.1lf\n",sol);
    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;
}