(x+yi) \cdot (cos \theta+sin \theta)表示在复平面上将(x,y)绕原点逆时针旋转θ。那么(x,y)绕原点逆时针旋转θ后得到的点就是(x cos \theta-y sin \theta,x sin \theta+y cos \theta)。
　　θ可以很容易的得出。将给出的一个点绕多边形中心不断旋转θ，即可得到正多边形。
　　这题的正多边形中心并不是原点，所以还要想办法把中心求出来，才能用上面的公式。
sgu120_1sgu120_2
　　这里，N1代表编号较小的点，根据N1和N2的位置关系，有上面两种情况。但O点的求法可以统一为，将向量P逆时针旋转θ（这个θ跟前面旋转公式里的θ没有关系），然后将长度放大1 \over {cos \theta}。化简得到O=(x_M-y_P tan \theta,x_P tan \theta+y_M)。
　　Submit 1: WA on 2。好像精度不够，比如这组数据得到的结果就很糟：

6 1 4
0 10
0 -10

-0.000000 10.000002
8.660255 5.000001
8.660255 -5.000000
0.000000 -10.000001
-8.660254 -5.000000
-8.660254 5.000000

　　不仅如此，还写出了这样的语句，让相关变量互相更新：O.x=O.x-O.y*tanth; O.y=O.x*tanth+O.y;
　　精度的问题是因存储各点的坐标时误用float类型产生的。
　　Submit 2: WA on 6。精度仍然有问题，有些应该输出0.000000的地方输出-0.000000。不过发现一个AC的标程也有这样的问题。求O点的地方写错了。
　　Submit 3: WA on 2。求O点的地方又写错了。
　　Submit 4: WA on 6。MaShuo提出，π的定义应该用系统函数或者系统常量，不要写3.14...。他认为自己写3.14...的话，在后面的三角函数运算中会产生很大的误差。
　　Submit 5: WA on 6。实在不知道为什么错了，开始使用“控制变量法”——用标程中的关键语句代替我的程序中的语句，逐步找出问题所在。这次更换我的程序中旋转给出点的方法——从逆时针旋转改到顺时针旋转。
　　Submit 6: WA on 1。有个n1+1写成了n2-1，是由于替换不完善造成的。
　　Submit 7: WA on 2。算O点用到的θ错了。
　　Submit 8: WA on 6。θ还是错的。
　　Submit 9: WA on 2。θ还是错的。
　　Submit 10: AC。不容易啊……交了10次才过……

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
 
#define PI 3.1415926535897932
 
struct point
{
    double x,y;
};
 
inline double format(double a)
{
    return fabs(a)<1e-7?0:a;
}
 
int main()
{
    point O,point1,point2,points[151];
    int n,n1,n2;
    scanf("%d%d%d",&n,&n1,&n2);
    scanf("%lf%lf%lf%lf",&point1.x,&point1.y,&point2.x,&point2.y);
    if (n2<n1)
    {
        swap(n1,n2); swap(point1,point2);
    }
    point mid={(point1.x+point2.x)/2,(point1.y+point2.y)/2};
    double theta=PI*(n2-n1)/n;
    if (n2-n1<n/2) theta+=PI*3/2;
    else theta-=PI/2;
    double tanth=tan(theta);
    O.x=mid.x-(mid.y-point1.y)*tanth; O.y=(mid.x-point1.x)*tanth+mid.y;
    points[n1].x=point1.x-=O.x; points[n1].y=point1.y-=O.y;
    double sina=sin(PI*2/n),cosa=cos(PI*2/n);
    for (int i=1,j=n1+1;i<n;i++,j++)
    {
        if (j>n) j-=n;
        points[j].x=+point1.x*cosa+point1.y*sina; points[j].y=-point1.x*sina+point1.y*cosa;
        point1=points[j];
    }
    for (int i=1;i<=n;i++) printf("%.6lf %.6lf\n",format(points[i].x+O.x),format(points[i].y+O.y));
    return 0;
}