Cod sursa(job #67329)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 24 iunie 2007 12:08:30
Problema Gradina Scor Ascuns
Compilator cpp Status done
Runda Marime 1.6 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define f first
#define s second
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define PII pair <int,int>
#define nmax 512

typedef long long lint;

int m,n[2],st[nmax],p[nmax];
lint S[2],sol;
char viz[nmax],pz[nmax],nw[nmax];
PII P[nmax],A[2][nmax];

int smn(PII A,PII B,PII C)
{
    B.f-=A.f, B.s-=A.s;
    C.f-=A.f, C.s-=A.s;
    return (lint)B.f*C.s-(lint)B.s*C.f>0;
}

int doit(int z)
{
    int i,k=0;
    memset(viz,0,sizeof(viz));
    FOR(i,1,n[z])
    {
	for(;k&&smn(A[z][st[k-1]],A[z][st[k]],A[z][i]);viz[st[k--]]=0);
	viz[st[++k]=i]=1;
    }
    for(S[z]=0,i=n[z]-1;i>=0;--i)
    {
	if(viz[i])
	    continue;
	for(;k&&smn(A[z][st[k-1]],A[z][st[k]],A[z][i]);viz[st[k--]]=0);
	viz[st[++k]=i]=1;
    }
    FOR(i,0,n[z])
	S[z]+=(lint)A[z][st[i]].f*A[z][st[i+1]].s-(lint)A[z][st[i]].s*A[z][st[i+1]].f;
    S[z]=abs(S[z]);
    return k==n[z];
}

bool cmp(const int i,const int j)
{
    return P[i]<P[j];
}

int main()
{
    int i,j,k,x;
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    scanf("%d",&m);
    FOR(i,0,m)
	scanf("%d %d",&P[i].f,&P[i].s),p[i]=i;
    sort(p,p+m,cmp);
    sort(P,P+m);

    sol=1000111000;
    FOR(i,0,m) FOR(j,0,m) 
	if(j!=i)
	{
	    n[0]=n[1]=0;
	    FOR(k,0,m)
	    {
		if(i!=k&&j!=k)
		    x=smn(P[i],P[j],P[k]);
		else
		    x=(i==k?1:0);
		A[x][n[x]++]=P[k],nw[p[k]]=(x?'I':'V');
	    }
	    if(doit(0)&&doit(1))
		if(sol>abs(S[0]-S[1])||(sol==abs(S[0]-S[1])&&strcmp(nw,pz)==-1))
	    {
		sol=abs(S[0]-S[1]);
		memcpy(pz,nw,sizeof(nw));
	    }
	}
    printf("%.1lf\n%s\n",sol/2.0,pz);
    return 0;
}