题意
给出一正多边形三顶点的坐标，求此正多边形的面积最小值。
分析
为了叙述方便，定义正多边形的单位圆心角 $u$ 为正多边形的某条边对该正多边形外心（外接圆的圆心）所张的角（即外接圆的某条弦所对的圆心角）。
- 多边形的边数未知，但其外接圆是确定的。多边形的外接圆即三个顶点所构成三角形的外接圆。面积最小即边数最少，单位圆心角最大。
- 设三角形某两边所对的圆心角为 $a_1$，$a_2$ (expressed in radians)，则最大单位圆心角为 $u= \gcd(a_1, a_2, 2\pi-a_1-a_2)$
思路
- 三点定圆。两线段中垂线交点即为圆心。若线段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)$$ 此式形式十分对称，便于记忆。解方程组即得圆心坐标。
- 求两正实数的最大公约数（gcd）。
- 求正多边形的面积。
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define dis2(p) (p.X*p.X+p.Y*p.Y)
#define det(i, j) (eq[0][i]*eq[1][j]-eq[0][j]*eq[1][i])
#define ang(p) atan2(p.Y, p.X)
#define eps 1e-4
#define PI 3.14159263558979323846
typedef double db;
typedef pair<db, db> P;
P p[];
//make sure that your algorithm is correct
db get_ang(P v1, P v2){
return acos((v1.X*v2.X+v1.Y*v2.Y)/dis2(v1));
}
P get_center(){
db eq[][];
for(int i=; i<; i++){
eq[i][]=*(p[i].X-p[i+].X);
eq[i][]=*(p[i].Y-p[i+].Y);
eq[i][]=dis2(p[i])-dis2(p[i+]);
}
return mp(det(, )/det(, ), det(, )/det(, ));
} P operator - (const P &a, const P &b){
return mp(a.X-b.X, a.Y-b.Y);
} db gcd(db a, db b){
return b<eps?a:gcd(b, fmod(a, b));
} int main(){
//freopen("in", "r", stdin);
for(int i=; i<; i++)
scanf("%lf%lf", &p[i].X, &p[i].Y);
P center=get_center();
P v[];
for(int i=; i<; i++)
v[i]=p[i]-center;
db a1=get_ang(v[], v[]);
db a2=get_ang(v[], v[]);
db a3=*PI-a1-a2;
db tmp=gcd(gcd(a1, a2), a3);
db res=PI/tmp*dis2(v[])*sin(tmp);
printf("%.8f\n", res);
return ;
}
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 <bits/stdc++.h>
using namespace std; using ll=long long; ll pow(int x, int n, int mod){
ll res=;
for(; n; ){
if(n&) res*=x, res%=mod;
x*=x, x%=mod, n>>=;
}
return res;
} ll inv(int x, int p){
return pow(x, p-, 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+; int res=; int m=min(*k, n);
k=min(k, n); for(int s=; s<<<m; s++){
int ones=;
for(int i=; i<m; i++)
ones+=bool(s&<<i);
int tmp=; if(ones==k){
for(int i=; i<m; i++)
if(s&<<i)
tmp=lcm(tmp, n-i, mod);
res=max(res, tmp);
}
}
cout<<res<<endl;
return ;
}