Ευκλειδης 原题地址 1. 题意：给定三个点，求可以构成的最小正n边形的边数。 2. 思路分析： 先把距离以及角度的函数写出，方便以后处理； 由余弦定理可以求出这三条边对应的角
Ευκλειδης
原题地址
1. 题意：给定三个点，求可以构成的最小正n边形的边数。
2. 思路分析：
先把距离以及角度的函数写出，方便以后处理；
由余弦定理可以求出这三条边对应的角度。对于正 n 边形，每个圆心角为 1/n 2 pi,当我们用每条边对应的圆心角/3~1000内的多边形的圆心角，如果可以整除，那么就是最小的边数。注意：我们求的角度是圆周角=圆心角/2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define maxn 200005
const int mod=1e9+7;
#define eps 1e-6
#define pi acos(-1.0)
bool zero(double n){
return n<eps&&n>-eps;
}
double dis (double x1,double y1,double x2,double y2){
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double ang(double a,double b,double c){
return acos( (a*a+b*b-c*c)/(2*a*b) );
}
bool check (double n){
return zero(n-(int)(n+0.5));
}
ll quipow(ll a,ll b){
ll ans=0;
while(b>0){
if(b%2)ans=ans*a;
b=b/2;
a=a*a;
}
return ans;
}
int main(){
double x[3],y[3],a,b,c,A,B,C;
int i,j;
for(i=0;i<3;i++){
cin>>x[i]>>y[i];
}
a=dis(x[0],y[0],x[1],y[1]);
b=dis(x[0],y[0],x[2],y[2]);
c=dis(x[1],y[1],x[2],y[2]);
A=ang(a,b,c)/pi;
B=ang(b,c,a)/pi;
C=ang(c,a,b)/pi;
for(i=3;i<=2000;i++){
if(check(A*i)&&check(B*i)&&check(C*i))break;
}
cout<<i<<endl;
}