首页 > ACM题库 > HDU-杭电 > HDU 4195-Regular Convex Polygon-计算几何-[解题报告]HOJ
2015
05-23

HDU 4195-Regular Convex Polygon-计算几何-[解题报告]HOJ

Regular Convex Polygon

问题描述 :

A regular convex polygon is a polygon where each side has the same length, and all interior angles are equal and less than 180 degrees. A square, for example, is a regular convex polygon. You are given three points which are vertices of a regular convex polygon R; can you determine the minimum number of vertices that R must have?

输入:

Each test case consists of three lines. Line i consists of two floating point values xi and yi (-104 <=xi,yi<=104) where (xi,yi) are the coordinates of a vertex of R. The coordinates are given with a precision of 10-6, i.e., they di ffer from the exact coordinates by at most 10-6. You may assume that for each test case the Euclidean distance between any two given points is at least 1, and R has at most 1000 vertices. The input will finish with a line containing the word END.

输出:

Each test case consists of three lines. Line i consists of two floating point values xi and yi (-104 <=xi,yi<=104) where (xi,yi) are the coordinates of a vertex of R. The coordinates are given with a precision of 10-6, i.e., they di ffer from the exact coordinates by at most 10-6. You may assume that for each test case the Euclidean distance between any two given points is at least 1, and R has at most 1000 vertices. The input will finish with a line containing the word END.

样例输入:

-1385.736326 -146.954822
430.000292 -2041.361203
1162.736034 478.316025
0.000000 4147.000000
-4147.000000 0.000000
0.000000 -4147.000000
END

样例输出:

3
4

题意:给你三个顶点,这三个点是一个正多边形上的顶点,问这个正多边形最少有多少个边?

思路:三个点,三角形–>外接圆–>必定也是该凸多边形的外接圆-
我们可以把三个点当做一个三角形放在它的外接圆上,然后求出每个角的度(即三角形分的三个弧度所对应的圆周角),设顶点数为n,我们只需计算,三角形任意两点所对应的圆心角是否是2PI/n的倍数就可以了,并且i很小,可以枚举。

#include <stdio.h>
#include <math.h>

//注意精度,1e-8直接WA了一次
#define EPS 1e-6
#define PI acos(-1.0)

double dist[3],angle[3];
double point[3][2];

double cal_dist(int i,int j)
{
    return sqrt((point[i][0] - point[j][0]) * (point[i][0] - point[j][0]) + (point[i][1] - point[j][1]) * (point[i][1] - point[j][1]));
}
///求圆周角
double cal_angle(int i,int j,int k)
{
    return acos((dist[i] * dist[i] + dist[j] * dist[j] - dist[k] * dist[k])/(2.0 * dist[i] * dist[j]));
}
///判断是否为整数,记得加0.05,注意 1 可能被表示成0.99999999999
bool ok(double x)
{
    return fabs(x - int(x + 0.05)) < EPS;
}
int main()
{
    int i;
    while(scanf("%lf%lf",&point[0][0],&point[0][1]) == 2)
    {
        scanf("%lf%lf%lf%lf",&point[1][0],&point[1][1],&point[2][0],&point[2][1]);
        dist[0] = cal_dist(0,1);
        dist[1] = cal_dist(1,2);
        dist[2] = cal_dist(0,2);

        angle[0] = cal_angle(0,1,2) / PI;
        angle[1] = cal_angle(1,2,0) / PI;
        angle[2] = cal_angle(2,0,1) / PI;

        for(i = 3; i <= 1000; ++i)
            if(ok(angle[0] * i) && ok(angle[1] * i) && ok(angle[2] * i))
                break;
        printf("%d\n",i);
    }
    return 0;
}

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

参考:http://blog.csdn.net/cscj2010/article/details/7781029