Cod sursa(job #536644)

Utilizator AndreyPAndrei Poenaru AndreyP Data 18 februarie 2011 21:36:35
Problema Gradina Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.75 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define N 256
#define ll long long
struct pii {
	int fs,sc;
};

int n;
pii p[N];
int pi[N],pi1[N];
int p1[N],p2[N];
int v1[N],v2[N];
int st[N];
ll rez = 1LL<<62;
char rez1[N],rez2[N];
bitset< N > uz;

inline void citire() {
	scanf("%d",&n);
	
	for(int i=1; i<=n; ++i) {
		pi[i] = i;
		scanf("%d%d",&p[i].fs,&p[i].sc);
	}
}

bool compar(const int &x,const int &y) {
	if(p[x].fs<p[y].fs)
		return true;
	if(p[x].fs>p[y].fs)
		return false;
	return (p[x].sc<p[y].sc);
}

inline bool semn(int a,int b,int c) {
	ll A = p[a].sc-p[b].sc;
	ll B = p[b].fs-p[a].fs;
	ll C = (ll)p[a].fs*(ll)p[b].sc-(ll)p[b].fs*(ll)p[a].sc;
	
	if(A*(ll)p[c].fs+B*(ll)p[c].sc+C>0)
		return false;
	return true;
}

inline bool infas(int p1[N],ll &A) {
	A = 0;
	uz.reset();
	st[0] = 2;
	st[1] = 1;
	st[2] = 2;
	uz[2] = 1;
	int pas = 1,i=3;
	
	while(!uz[1]) {
		while(uz[i]) {
			if(i==p1[0])
				pas = -1;
			i += pas;
		}
		
		while(st[0]>1 && semn(p1[st[st[0]-1]],p1[st[st[0]]],p1[i]))
			uz[st[st[0]--]] = 0;
		st[++st[0]] = i;
		uz[st[st[0]]] = 1;
	}
	
	if(st[0]!=p1[0]+1)
		return false;
	
	pii x,y;
	for(int i=1; i<st[0]; ++i) {
		x = p[p1[st[i]]];
		y = p[p1[st[i+1]]];
		A += (ll)x.fs*(ll)y.sc-(ll)x.sc*(ll)y.fs;
	}
	
	if(A<0LL)
		A = -A;
	return true;
}

inline void adauga(int p[N],int v[N],int x,int y) {
	p[0] = 0;
	int i;
	
	if(x==-1) {
		for(i=1; i<=v[0]; ++i)
			p[++p[0]] = v[i];
		return;
	}
	
	for(i=1; i<=v[0] && pi1[v[i]]<pi1[x]; ++i)
		p[++p[0]] = v[i];
	p[++p[0]] = x;
	
	if(y==-1) {
		for(; i<=v[0]; ++i)
			p[++p[0]] = v[i];
		return;
	}
	
	for(; i<=v[0] && pi1[v[i]]<pi1[y]; ++i)
		p[++p[0]] = v[i];
	p[++p[0]] = y;
	for(; i<=v[0]; ++i)
		p[++p[0]] = v[i];
}
	
inline void vezi() {
	ll a1,a2;
	if(infas(p1,a1)==false)
		return;
	if(infas(p2,a2)==false)
		return;
	
	a1 -= a2;
	if(a1<0LL)
		a1 = -a1;
	bool da = false;
	if(a1<rez) {
		rez = a1;
		
		for(int i=1; i<=p1[0]; ++i) {
			if(p1[i]==1) {
				da = true;
				break;
			}
		}
		
		char c1,c2;
		if(da) {
			c1 = 'I';
			c2 = 'V';
		} else {
			c1 = 'V';
			c2 = 'I';
		}
		
		for(int i=1; i<=p1[0]; ++i)
			rez1[p1[i]] = c1;
		for(int i=1; i<=p2[0]; ++i)
			rez1[p2[i]] = c2;
	} else
	if(a1==rez) {
		for(int i=1; i<=p1[0]; ++i) {
			if(p1[i]==1) {
				da = true;
				break;
			}
		}
		
		char c1,c2;
		if(da) {
			c1 = 'I';
			c2 = 'V';
		} else {
			c1 = 'V';
			c2 = 'I';
		}
		
		for(int i=1; i<=p1[0]; ++i)
			rez2[p1[i]] = c1;
		for(int i=1; i<=p2[0]; ++i)
			rez2[p2[i]] = c2;
		
		for(int i=1; i<=n; ++i) {
			if(rez1[i]==rez2[i])
				continue;
			if(rez1[i]<rez2[i])
				return;
			memcpy(rez1+1,rez2+1,n);
			return;
		}
	}
}

inline void part(int x,int y) {
	v1[0] = v2[0] = 0;
	
	for(int i=1; i<=n; ++i) {
		if(pi[i]==x || pi[i]==y)
			continue;
		if(semn(x,y,pi[i]))
			v1[++v1[0]] = pi[i];
		else
			v2[++v2[0]] = pi[i];
	}
	
	adauga(p1,v1,-1,-1);
	adauga(p2,v2,x,y);
	if(p1[0]>2 && p2[0]>2)
		vezi();
	
	adauga(p1,v1,x,-1);
	adauga(p2,v2,y,-1);
	if(p1[0]>2 && p2[0]>2)
		vezi();
	
	adauga(p1,v1,y,-1);
	adauga(p2,v2,x,-1);
	if(p1[0]>2 && p2[0]>2)
		vezi();
	
	adauga(p1,v1,x,y);
	adauga(p2,v2,-1,-1);
	if(p1[0]>2 && p2[0]>2)
		vezi();
}

int main() {
	freopen("gradina.in","r",stdin);
	freopen("gradina.out","w",stdout);
	
	citire();
	
	sort(pi+1,pi+n+1,compar);
	for(int i=1; i<=n; ++i)
		pi1[pi[i]] = i;
	
	for(int i=1; i<n; ++i) {
		for(int j=i+1; j<=n; ++j)
			part(pi[i],pi[j]);
	}
	
	if((rez&1)==1)
		printf("%lld.5\n",rez/2);
	else
		printf("%lld.0\n",rez/2);
	rez1[n+1] = '\n';
	rez1[n+2] = '\0';
	fputs(rez1+1,stdout);
	
	return 0;
}