| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
花了很长时间,终于ac了,供大家参考#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator