http://jsj.sdibt.edu.cn/judge/problem/viewProblem.action?id=186
题目大意:给定一个圆的直径d,以及均匀分布在圆上的n个点,从这n个点中,根据规则(g*k)%n[其中k=0,1,…,c-1]从这n个点中选出c个点,在这c个可用点上放置4个音箱,使这由这个4个音箱构成的四边形的面积最大。
输入输出:
输入:第一行是测试数据的组数,后面每一行4个数分别代表圆的直径d,n,c和g,其中:
1<=d<=1000
4<=n<=10^9
4<=c<=1000且c<=n
1<=g<=n
输出:
Scenario #i:(i代表测试数据组号)
最大的面积(保留6位小数)
解题思路:
1.计算几何的题目,属于高精度运算。
2.首先计算出可用点并将可用点按从小到大的顺序排列

for(j=1;j<c;j++)
			suits[j]=(suits[j-1]+g)%n;
		sort(suits,suits+c);

3.然后计算可用点的坐标(圆心为原点坐标)

for(j=0;j<c;j++)
		{
			angle=2.0*PI/n*suits[j];
			x[j]=sin(angle)*d/2.0;
			y[j]=cos(angle)*d/2.0;
		}

4.坐标确定之后就可以开始求最大面积了,计算面积的策略是这样的:每次第一个可用点都做为4个顶点中的一个,然后取它的对角线顶点从1到c-1。然后先求出顶点编号比j小的三角形的面积中最大的那个,然后再求出顶点编号比j大的三角形的面积中最大的那个,这两三角形的和即是i,j为一条对角线的四边形中面积最大的。(因为j是一样的,所以保证两个三角形会构成四边形)

res=0;
		//计算最大面积
		for(j=1;j<c;j++)//因为j是一样的,所以能保证两个三角形能组成一个四边形
		{
			first=0;
			for(k=1;k<j;k++)//计算第j个点前最大的三角形面积
			{
				tmp=area(k,j);
				if(tmp>first)
					first=tmp;
			}
			for(k=j+1;k<c;k++)//计算第j个点后的最大的三角形面积
			{
				tmp=area(j,k);
				if(first+tmp>res)
					res=first+tmp;
			}
		}

5.循环结束输出最大值即可
注意:中间的PI精度至少到3.1415926535898
附:已知三角行三个顶点a(x1,y1),b(x2,y2),c(x3,y3)坐标三角形的面积计算公式:
S=((x1*y2-x2*y1)+(x2*y3-x3*y2)+(x1*y3-x3*y1))/2。

发表评论

电子邮件地址不会被公开。

Post Navigation