首页 > ACM题库 > HDU-杭电 > HDU 2826-The troubles of lmy[解题报告]HOJ
2014
02-17

HDU 2826-The troubles of lmy[解题报告]HOJ

The troubles of lmy

问题描述 :

Lmy is the lovely cousin of zmq, and she’s a junior high school student. One day she came back from school.
Zmq: What did you learn in your class today?
Lmy: Similar triangle.
Zmq: Well, fine, have you mastered it?
Lmy: Sure, that’s a piece of cake.
Zmq: OK, well, let me test you to see whether you have thoroughly understood the conception of being similar. I’ll draw two Arbitrary Polygons, and you have to tell me whether they are similar or not. If you are right, I’ll take you out.
Lmy: ……
It seems that little lmy got into troubles. Can you help her out by designing a program?

输入:

There are several test cases in the input.
The first line of each case is an n (n <= 300), indicating that each polygon has n points. And in the following 2n lines, each line represents a point. The first n point represents the first polygon in anti-clockwise order, and so the second. Please note that all the polygons are simple.
You can try to rotate them, then tell whether they are similar or not.

输出:

There are several test cases in the input.
The first line of each case is an n (n <= 300), indicating that each polygon has n points. And in the following 2n lines, each line represents a point. The first n point represents the first polygon in anti-clockwise order, and so the second. Please note that all the polygons are simple.
You can try to rotate them, then tell whether they are similar or not.

样例输入:

3
0 0
1 1
0 1
0 0
2 2
0 2
3
0 0
1 1
0 1
0 0
2 2
0 1

样例输出:

Yes
No

#include<cstdio> 
int main() 
{ 
 int a[301][3],b[300][3]; 
 int i,j,n,k,flag; 
 double c[301]; 
 while(scanf("%d",&n)!=EOF) 
 { 
 flag=0; 
 k=0; 
 for(i=0;i<n;i++) 
 scanf("%d%d",&a[i][0],&a[i][1]); 
 for(i=0;i<n;i++) 
 scanf("%d%d",&b[i][0],&b[i][1]); 
 for(i=0;i<n;i++) 
 { 
 for(j=0;j<2;j++) 
 { 
 if(a[i][j]==0&&b[i][j]!=0) flag=1; 
 if(a[i][j]!=0&&b[i][j]==0) flag=1; 
 if(a[i][j]!=0&&b[i][j]!=0) 
 c[k++]=(double)a[i][j]/(double)b[i][j]; 
 } 
 } 
 for(i=0;i<k-1;i++) 
 if(c[i]!=c[i+1]) {flag=1;break;} 
 if(flag) 
 printf("No\n"); 
 else 
 printf("Yes\n"); 
 } 
 return 0; 
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法