题意

给出一正多边形三顶点的坐标，求此正多边形的面积最小值。

分析

为了叙述方便，定义正多边形的单位圆心角 $u$ 为正多边形的某条边对该正多边形外心（外接圆的圆心）所张的角（即外接圆的某条弦所对的圆心角）。

1. 多边形的边数未知，但其外接圆是确定的。多边形的外接圆即三个顶点所构成三角形的外接圆。面积最小即边数最少，单位圆心角最大。
2. 设三角形某两边所对的圆心角为 $a_1$，$a_2$ (expressed in radians)，则最大单位圆心角为 $u= \gcd(a_1, a_2, 2\pi-a_1-a_2)$

思路

1. 三点定圆。两线段中垂线交点即为圆心。若线段AB两端点的坐标分别为 A $(x_1, y_1)$， B $(x_2, y_2)$，则AB的中垂线方程为 $$2(x_1-x_2) x + 2(y_1-y_2) y = (x_1^2+y_1^2) - (x_2^2+y_2^2)$$ 此式形式十分对称，便于记忆。解方程组即得圆心坐标。
2. 求两正实数的最大公约数（gcd）。
3. 求正多边形的面积。

 

1 #include
     
       2 using namespace std; 3 #define X first 4 #define Y second 5 #define mp make_pair 6 #define dis2(p) (p.X*p.X+p.Y*p.Y) 7 #define det(i, j) (eq[0][i]*eq[1][j]-eq[0][j]*eq[1][i]) 8 #define ang(p) atan2(p.Y, p.X) 9 #define eps 1e-410 #define PI 3.14159263558979323846 11 typedef double db;12 typedef pair
      
        P;13 P p[3];14 //make sure that your algorithm is correct15 db get_ang(P v1, P v2){16     return acos((v1.X*v2.X+v1.Y*v2.Y)/dis2(v1));17 }18 P get_center(){19     db eq[2][3];20     for(int i=0; i<2; i++){21         eq[i][0]=2*(p[i].X-p[i+1].X);22         eq[i][1]=2*(p[i].Y-p[i+1].Y);23         eq[i][2]=dis2(p[i])-dis2(p[i+1]);24     }25     return mp(det(2, 1)/det(0, 1), det(0, 2)/det(0, 1));26 }27 28 P operator - (const P &a, const P &b){29     return mp(a.X-b.X, a.Y-b.Y);30 }31 32 db gcd(db a, db b){33     return b
      
     

 

P.S. 这道题还有更简便的解法，不必求外接圆圆心坐标，也不必求圆心角。有下列结论

设题中给出的三点所成三角形的三内角分别为 $A，B，C$ (expressed in radians） 则 $u$ 的最大值为

$$ 2 \gcd(A, B, C) $$

（此式与前面给出的表达式是一致的）

$A, B, C$ 可由余弦定理求得。还要求出三角形外接圆半径 $R$，可利用公式 $ R = \dfrac{abc}{4S}$，$a, b, c$ 为三边长，$S$ 为面积。

 

#include 
     
      using namespace std;using ll=long long;ll pow(int x, int n, int mod){    ll res=1;    for(; n; ){        if(n&1) res*=x, res%=mod;        x*=x, x%=mod, n>>=1;    }    return res;}ll inv(int x, int p){    return pow(x, p-2, p);}ll lcm(ll x, ll y, int p){    return x*y%p*inv(__gcd(x, y), p)%p;}int main(){    int n, k;    cin>>n>>k;    const int mod=1e9+7;    int res=0;    int m=min(2*k, n);    k=min(k, n);    for(int s=0; s<1<