Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

花了很长时间,终于ac了,供大家参考

Posted by wang898jian at 2014-09-11 22:56:06 on Problem 1021
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define max 100
#define media 20

class block
{
public:
	//num4Member总指向末尾元素的下一个为空的元素
	int num4Member;
	int elemet[max];
	int x[max];
	int y[max];

	int calEntropy();
	
	block();
protected:
private:
};

class arrow
{
public:
	int width,highth,pairNumb;
	int x[max];
	int y[max];
	block n[media];
	int num4Block;
	int entropy4Block[media];

	void devideBlock();	
	void calEntropy();
	void combineBlock();
	arrow();

protected:
private:
};

class game
{
public:
	int width,highth,pairNumb;
	arrow leftArrow;
	arrow rightArrow;

	void initArrow();
	bool compare();
protected:
private:
};

int main()
{
	//data structure
	int numCase=0;

	
	//input
	cin>>numCase;
	game Game[20];
	for (int i=0;i<numCase;i++)
	{
		cin>>Game[i].width>>Game[i].highth>>Game[i].pairNumb;
		for (int j=0;j<Game[i].pairNumb;j++)
		{
			cin>>Game[i].leftArrow.x[j]>>Game[i].leftArrow.y[j];
		}
		for (int k=0;k<Game[i].pairNumb;k++)
		{
			cin>>Game[i].rightArrow.x[k]>>Game[i].rightArrow.y[k];
		}

		//devide into blocks
		Game[i].initArrow();
		Game[i].leftArrow.devideBlock();
		Game[i].rightArrow.devideBlock();
		Game[i].leftArrow.combineBlock();
		Game[i].leftArrow.combineBlock();
		Game[i].leftArrow.combineBlock();
		Game[i].leftArrow.combineBlock();
		Game[i].rightArrow.combineBlock();
		Game[i].rightArrow.combineBlock();
		Game[i].rightArrow.combineBlock();
		Game[i].rightArrow.combineBlock();
		Game[i].leftArrow.calEntropy();
		Game[i].rightArrow.calEntropy();
	}
	for (int i=0;i<numCase;i++)
	{
		if (Game[i].compare())
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}
}
void game::initArrow()
{
	leftArrow.width=width;
	leftArrow.highth=highth;
	leftArrow.pairNumb=pairNumb;

	rightArrow.width=width;
	rightArrow.highth=highth;
	rightArrow.pairNumb=pairNumb;
}
bool game::compare()
{
	//if (leftArrow.num4Block!=rightArrow.num4Block)
	//{
	//	return false;
	//}
	for (int i=0; i<leftArrow.num4Block; i++)
	{
		if (leftArrow.entropy4Block[i] !=rightArrow.entropy4Block[i])
		{
			return false;
		}
	}
	return true;
}
void arrow::devideBlock()
{
	for (int i=0,blockElement=0;i<pairNumb;i++)
	{
		if (i==0)
		{
			n[i].elemet[i]=i;
			n[i].x[i]=x[i];
			n[i].y[i]=y[i];
			n[i].num4Member++;
			num4Block++;
			continue;
		}
		int flag4existBlock=0;
		for(int j=0;j<num4Block;j++)
		{
			for (int k=0; k<n[j].num4Member; k++)
			{
				if (( abs( x[i] - x[n[j].elemet[k]] )==1 && abs( y[i] - y[n[j].elemet[k]] )==0 )||
					( abs( x[i] - x[n[j].elemet[k]] )==0 && abs( y[i] - y[n[j].elemet[k]] )==1 ))
				{
					flag4existBlock=1;
					break;
				}
			}
			if (flag4existBlock==1)
			{
				n[j].elemet[n[j].num4Member]=i;
				n[j].x[n[j].num4Member]=x[i];
				n[j].y[n[j].num4Member]=y[i];
				n[j].num4Member++;
				break;
			}
		}
		if (flag4existBlock==0)
		{
			n[num4Block].elemet[0]=i;
			n[num4Block].x[0]=x[i];
			n[num4Block].y[0]=y[i];
			n[num4Block].num4Member++;
			num4Block++;
		}
	}
}
void arrow::combineBlock()
{
	for ( int i=0; i<num4Block-1; i++ )
	{
		if (n[i].num4Member<=1)
		{
			continue;
		}
		for ( int j=i+1; j<num4Block; j++ )
		{
			if (n[j].num4Member<1)
			{
				continue;
			}
			bool flag4existBlock=0;
			for (int k=0;k<n[i].num4Member;k++)
			{
				for (int l=0;l<n[j].num4Member;l++)
				{
					if (( abs( n[i].x[k] - n[j].x[l] )==1 && abs( n[i].y[k] - n[j].y[l] )==0 )||
						( abs( n[i].x[k] - n[j].x[l] )==0 && abs( n[i].y[k] - n[j].y[l] )==1 ))
					{
						flag4existBlock=1;
						for (int m=0;m<n[j].num4Member;m++)
						{
							n[i].elemet[n[i].num4Member+m]=n[j].elemet[m];
							n[i].x[n[i].num4Member+m]=n[j].x[m];
							n[i].y[n[i].num4Member+m]=n[j].y[m];
						}
						n[i].num4Member+=n[j].num4Member;
						n[j].num4Member=0;
						break;
					}
				}
				if (flag4existBlock==1)
				{
					break;
				}
			}
		}
	}
}
void arrow::calEntropy()
{
	for ( int i=0; i<num4Block; i++ )
	{
		entropy4Block[i] = n[i].calEntropy();
	}
	sort(entropy4Block,entropy4Block+num4Block);
	reverse(entropy4Block,entropy4Block+num4Block);
}
int block::calEntropy()
{
	int sum=0;
	for (int i=0;i<(num4Member-1);i++)
	{
		for (int j=i+1;j<num4Member;j++)
		{
			sum+=( (x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]) );
		}
	}
	return sum;
}
block::block()
{
	num4Member=0;
	memset(elemet,0,sizeof(elemet));
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));
}
arrow::arrow()
{
	width=0;
	highth=0;
	pairNumb=0;
	num4Block=0;
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));
	memset(entropy4Block,0,sizeof(entropy4Block));
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator