Cod sursa(job #487035)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 23 septembrie 2010 17:11:24
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.03 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define MAXN 260
using namespace std;
int N,NPlanePoints,NStack;
struct point{
	int x,y,nr;
} Points[MAXN];

int PlanePoints[MAXN];
int PointsStack[MAXN];

long long mindiffarea;
int Solution[MAXN],PartSol[MAXN];
bool DefArea;

inline bool RightTurn(int p1,int p2,int p3){
	int x1=Points[p1].x-Points[p2].x;
	int x2=Points[p3].x-Points[p2].x;
	int y1=Points[p1].y-Points[p2].y;
	int y2=Points[p3].y-Points[p2].y;

	long long product=(long long)x1*(long long)y2-(long long)x2*(long long)y1;

	if (product<0) return false; else return true;
}

inline bool cmp(const point &A, const point &B){
	if (A.x!=B.x) return (A.x<B.x); else 
		return (A.y<B.y);
}

inline bool LessThan(){

	for (int i=1;i<=N;++i)
		if (PartSol[i]<Solution[i]) return true; else
			if (PartSol[i]>Solution[i]) return false;

	return false;
}

long long HullArea(){

	NStack=2;
	PointsStack[1]=PlanePoints[1];
	PointsStack[2]=PlanePoints[2];

	for (int i=3;i<=NPlanePoints;++i){
		PointsStack[++NStack]=PlanePoints[i];
		while (NStack>=3 && RightTurn(PointsStack[NStack-2],PointsStack[NStack-1],PointsStack[NStack])){
			PointsStack[NStack-1]=PointsStack[NStack];
			--NStack;
		}
	}

	PointsStack[++NStack]=PlanePoints[NPlanePoints-1];
	
	for (int i=NPlanePoints-2;i>=1;--i){
		PointsStack[++NStack]=PlanePoints[i];
		while (NStack>=3 && RightTurn(PointsStack[NStack-2],PointsStack[NStack-1],PointsStack[NStack])){
			PointsStack[NStack-1]=PointsStack[NStack];
			--NStack;
		}
	}

	if ((NStack-1) != NPlanePoints) return -1;

	long long area=0;

	for (int i=1;i<NStack;++i)
		area+=((long long)Points[PointsStack[i]].x+Points[PointsStack[i+1]].x)*
			((long long)Points[PointsStack[i+1]].y-Points[PointsStack[i]].y);

	return area;


	
}

void Split(int p1,int p2){

	long long A=Points[p1].y-Points[p2].y;
	long long B=Points[p2].x-Points[p1].x;
	long long C=(long long)Points[p1].x*Points[p2].y-(long long)Points[p2].x*Points[p1].y;
	
	NPlanePoints=0;
	for (int i=1;i<=N;++i)
		if (i!=p2)
			if (i==p1 || (A*Points[i].x+B*Points[i].y+C)<0)
				PlanePoints[++NPlanePoints]=i;

	if (NPlanePoints<3 || (N-NPlanePoints)<3) return ;

	long long FirstArea=HullArea();

	if (FirstArea==-1) return ;

	NPlanePoints=0;
	for (int i=1;i<=N;++i)
		if (i!=p1)
			if (i==p2 || (A*Points[i].x+B*Points[i].y+C)>0)

				PlanePoints[++NPlanePoints]=i;

	long long SecondArea=HullArea();

	if (SecondArea==-1) return ;

	long long DiffArea=FirstArea-SecondArea;
	if (DiffArea<0) DiffArea=-DiffArea;

	if (DefArea==false){
		DefArea=true;
		mindiffarea=DiffArea;
		for (int i=1;i<=N;++i)
			Solution[i]=2;

		for (int i=1;i<=NPlanePoints;++i)
			Solution[Points[PlanePoints[i]].nr]=1;

		if (Solution[1]==2)
			for (int i=1;i<=N;++i)
				Solution[i]=3-Solution[i];

		return ;
	}

	if (DiffArea<mindiffarea) {
		mindiffarea=DiffArea;
		for (int i=1;i<=N;++i)
			Solution[i]=2;
		
		for (int i=1;i<=NPlanePoints;++i)
			Solution[Points[PlanePoints[i]].nr]=1;

		if (Solution[1]==2)
			for (int i=1;i<=N;++i)
				Solution[i]=3-Solution[i];

		return ;
	}

	if (DiffArea==mindiffarea){

		for (int i=1;i<=N;++i)
			PartSol[i]=2;

		for (int i=1;i<=NPlanePoints;++i)
			PartSol[Points[PlanePoints[i]].nr]=1;

		if (PartSol[1]==2)
			for (int i=1;i<=N;++i)
				PartSol[i]=3-PartSol[i];

		if (LessThan())
			for (int i=1;i<=N;++i) Solution[i]=PartSol[i];
	}
	
}

int main(){


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

	scanf("%d",&N);
	for (int i=1;i<=N;++i){
		scanf("%d%d",&Points[i].x,&Points[i].y);
		Points[i].nr=i;
	}

	sort(Points+1,Points+N+1,cmp);

	fclose(stdin);

	DefArea=false;


	for (int i=1;i<=N;++i)
		for (int j=1;j<=N;++j)
			if (i!=j) Split(i,j);

	printf("%lld",mindiffarea/2);
	if (mindiffarea%2) printf(".5"); else printf(".0");
	printf("\n");

	for (int i=1;i<=N;++i)
		if (Solution[i]==1) printf("I"); else printf("V");

	printf("\n");

	fclose(stdout);

	return 0;
}