首页 > ACM题库 > HDU-杭电 > HDU 4082-Hou Yi’s secret[解题报告]HOJ
2015
04-16

HDU 4082-Hou Yi’s secret[解题报告]HOJ

Hou Yi’s secret

问题描述 :

Long long ago, in the time of Chinese emperor Yao, ten suns rose into the sky. They burned the crops and scorched the bushes and trees, leaving the people with nothing to eat.
Qin Shi Huang's National Road System

Hou Yi was the greatest archer at that time. Yao wanted him to shoot down nine suns. Hou Yi couldn’t do that job with ordinary arrows. So Yao send him to God to get some super powerful magic arrows. Before Hou Yi left, Yao said to him: "In order to manage our country in a better way, I want to know how many years can I live from now on. Please ask God this question for me." Hou Yi promised him.
Hou yi came back from God with ten magic arrows. He shot down nine suns, and the world returned to harmony. When Yao asked Hou Yi about the answer of his question, Hou Yi said: "God told me nothing. But I happened to see a ‘life and death book’ with your name on it. So I know the answer. But you know, I can’t tell you because that’s God’s secret, and anyone who gives out God’s secret will be burned by a thunder!"
Yao was very angry, he shouted: "But you promised me, remember?" Hou Yi said:
"Ooo-er, let’s make some compromise. I can’t tell you the answer directly, but I can tell you by my only precious magic arrow. I’ll shoot the magic arrow several times on the ground, and of course the arrow will leave some holes on the ground. When you connect three holes with three line segments, you may get a triangle. The maximum number of similar triangles you can get means the number of years you can live from now on." (If the angles of one triangle are equal to the angles of another triangle respectively, then the two triangles are said to be similar.)
Yao was not good at math, but he believed that he could find someone to solve this problem. Would you help the great ancient Chinese emperor Yao?

输入:

There are multiple test cases, and the number of test cases is no more than 12.
The first line of every test case is an integer n meaning that Hou Yi had shot the magic arrow for n times (2 < n <= 18).
Then n lines follow. Each line contains two integers X and Y (-100 < X, Y < 100), the coordinate of a hole made by the magic arrow.
Please note that one hole can be the vertex of multiple triangles.
The input ends with n = 0.

输出:

There are multiple test cases, and the number of test cases is no more than 12.
The first line of every test case is an integer n meaning that Hou Yi had shot the magic arrow for n times (2 < n <= 18).
Then n lines follow. Each line contains two integers X and Y (-100 < X, Y < 100), the coordinate of a hole made by the magic arrow.
Please note that one hole can be the vertex of multiple triangles.
The input ends with n = 0.

样例输入:

3
1 1
6 5
12 10
4
0 0
1 1
2 0
1 -1
0

样例输出:

1
4

#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;
#define eps 1e-8
struct pot
{
	double x,y;
}point[30];
struct triange
{
	double a,b,c;
	int num;
}tri[20000];
int mark[300][300];
int judge(double x,double y)
{
	if(fabs(x-y)<=eps)
	return 1;
	return 0;
}
double xmulti(pot p1,pot p2,pot p0)
{
	return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
double getdis(pot a,pot b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int jsimlar(triange e,triange f)
{
	return judge(e.a*f.b,e.b*f.a)&&judge(e.b*f.c,e.c*f.b);
}
int main()
{
	int i,j,k,n,m,x,y,l;
	while(scanf("%d",&n),n)
	{
		memset(mark,0,sizeof(mark));
		k=0;l=0;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			if(mark[x+100][y+100]==0)
			{
				mark[x+100][y+100]=1;
				point[k].x=x;
				point[k].y=y;
				k++;
			}			
		}		
		n=k;
		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				for(k=j+1;k<n;k++)
				{
					m=xmulti(point[i],point[j],point[k]);
					if(judge(m,0)==0)
					{
						tri[l].a=getdis(point[i],point[j]);
						tri[l].b=getdis(point[i],point[k]);
						tri[l].c=getdis(point[j],point[k]);
						if(tri[l].a>tri[l].b)
						swap(tri[l].a,tri[l].b);
						if(tri[l].a>tri[l].c)
						swap(tri[l].a,tri[l].c);
						if(tri[l].b>tri[l].c)
						swap(tri[l].b,tri[l].c);
						tri[l].num=1;
						l++;
					}
				}
			}
		}
		
	//	printf("n=%d\n",n);
	//	printf("l=%d\n",l);
		for(i=0;i<l;i++)
			for(j=i+1;j<l;j++)
			{
				if(tri[i].num!=-1)
				{
					if(jsimlar(tri[i],tri[j]))
					{
						tri[i].num++;
						tri[j].num=-1;
					}
				}
			}
		int ans=0;
		for(i=0;i<l;i++)
		{
			if(ans<tri[i].num)
			ans=tri[i].num;
		}
		printf("%d\n",ans);
	}
	return 0;
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。