首页 > ACM题库 > HDU-杭电 > HDU 4033-Regular Polygon-数论-[解题报告]HOJ
2015
04-15

HDU 4033-Regular Polygon-数论-[解题报告]HOJ

Regular Polygon

问题描述 :

In a 2_D plane, there is a point strictly in a regular polygon with N sides. If you are given the distances between it and N vertexes of the regular polygon, can you calculate the length of reguler polygon’s side? The distance is defined as dist(A, B) = sqrt( (Ax-Bx)*(Ax-Bx) + (Ay-By)*(Ay-By) ). And the distances are given counterclockwise.

输入:

First a integer T (T≤ 50), indicates the number of test cases. Every test case begins with a integer N (3 ≤ N ≤ 100), which is the number of regular polygon’s sides. In the second line are N float numbers, indicate the distance between the point and N vertexes of the regular polygon. All the distances are between (0, 10000), not inclusive.

输出:

First a integer T (T≤ 50), indicates the number of test cases. Every test case begins with a integer N (3 ≤ N ≤ 100), which is the number of regular polygon’s sides. In the second line are N float numbers, indicate the distance between the point and N vertexes of the regular polygon. All the distances are between (0, 10000), not inclusive.

样例输入:

2
3
3.0 4.0 5.0
3
1.0 2.0 3.0

样例输出:

Case 1: 6.766
Case 2: impossible

题意:就是给你一个正多边形内的点到正多边形的顶点的距离,求出这个正多边形的边长。

成都网络赛题目,wa了一个下午,一直以为是精度问题,看完标程才知道不是,是题目的问题,如果按标程的解法就是直接二分枚举,判断角度之和等于2pi吗?这样做明显是错的,反例菱形,我就是考虑了这一点,结果wa 了一个下午,我的做法,判断每个顶角是否相等,结果就wa了。刚刚顺着解题报告写了,1y。坑爹啊。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4584550 2011-09-11 22:00:53 Accepted 4033 15MS 280K 1051 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const double PI=acos(0.0)*2;
int n;
double b[105];
double angle(double a,double b,double c)
{
	return acos((a*a+b*b-c*c)/2/a/b);
}
int OK(double mid)
{
	double ans=0;
	for(int i=0;i<n;i++)
	{
		if(b[i]+b[(i+1)%n]<=mid)
			return -1;
		if(fabs(b[i]-b[(i+1)%n])>=mid)
			return 0;
		ans+=angle(b[i],b[(i+1)%n],mid);
	}
	if(fabs(ans-2*PI)<0.000001)return 1;
	else
		if(ans-2*PI>0)return -1;
		else
			return 0;
}
int main()
{
	int T,t,flag;
	scanf("%d",&T);
	for( t=1;t<=T;t++)
	{
		flag=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%lf",&b[i]);
		}
		double r=20000,l=0,mid;
		printf("Case %d: ",t);
		while(r-l>0.000001)
		{
			mid=(l+r)/2;
			int kk=OK(mid);
			if(kk==1)
			{
				printf("%.3f\n",mid);
				flag=1;
				break;
			}
			else
				if(kk==0)
				   l=mid;
				else
					r=mid;
		}
		if(flag==0)printf("impossible\n");
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xymscau/article/details/6768108


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.