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