这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% fold 点击显/隐题目 %}
On one quiet day all of sudden Mister B decided to draw angle a on his field. Aliens have already visited his field and left many different geometric figures on it. One of the figures is **regular convex n-gon** (regular convex polygon with $n$ sides).
That's why Mister B decided to use this polygon. Now Mister B must find three distinct vertices v1, v2, v3 such that the angle ∠v1v2v3\angle v_1 v_2 v_3(where v2v_2 is the vertex of the angle, and v1v_1 and v3v_3 lie on its sides) is as close as possible to aa. In other words, the value $\left| \angle v_1 v_2 v_3 - a \right| $ should be minimum possible.
If there are many optimal solutions, Mister B should be satisfied with any of them.
First and only line contains two space-separated integers $n$ and $a$ ($3 \leq n \leq 10^5$, $1 \leq a \leq 180$) — the number of vertices in the polygon and the needed angle, in degrees.
Print three space-separated integers: the vertices v1, v2, v3, which form . If there are multiple optimal solutions, print any of them. The vertices are numbered from 1 to n in clockwise order.
3 15 4 67 4 68
1 2 3 2 1 3 4 1 2
题解
题意
正n边形选3个顶点,使拼合成的角使所有角中最接近a的
需要的数学知识:
正n边形内角和: (n−2)×180∘(n-2) \times 180^{\circ}
对于如图所示的角,其角度为 ((4−2)×180−2×(6−2)∗180÷6)÷2=60((4-2) \times 180 - 2 \times (6-2)*180 \div 6) \div 2 = 60
同样,可以证明（数学归纳法）得到 ∠v2v1vk(3≤k≤n)\angle v_2 v_1 v_k ( 3 \leq k \leq n ) 正好可以覆盖所有的可以取到的角度
所以,只要枚举 (i×180−i×(n−2)∗180÷n)÷2 (1≤i≤n−2)(i \times 180 - i \times (n-2)*180 \div n) \div 2 \:\:\: ( 1 \leq i \leq n-2 ) 即可
代码
{% fold 点击显/隐代码 %}```cpp Mister B and Angle in Polygon https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
using namespace std;
const double eps = 1e-5;
int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);
double n, a;
while (cin >> n >> a) {
double tot = 180 * (n - 2);
double t = tot / n;
double Min = 9e9;
double pos = 0;
for (int i = 1; i <= n - 2; i++) {
double temp = (180 * i - t * i) / 2;
//cout << "2 1 " << i + 2 << " " << temp << " " << fabs(temp - a)
//<< " "<<Min<<endl;
if (fabs(temp - a) < Min) {
Min = fabs(temp - a);
pos = i;
}
}
cout << "2 1 " << pos + 2 << endl;
}
#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}
{% endfold %}