题目

{% 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 $\angle v_1 v_2 v_3$ (where $v_2$ is the vertex of the angle, and $v_1$ and $v_3$ lie on its sides) is as close as possible to $a$ . 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

{% endfold %}

题解

题意
正 n 边形选3个顶点,使拼合成的角使所有角中最接近 a 的

需要的数学知识:
正n边形内角和: $(n-2) \times 180^{\circ}$

对于如图所示的角,其角度为 $((4-2) \times 180 - 2 \times (6-2)*180 \div 6) \div 2 = 60$

同样,可以证明（数学归纳法）得到 $\angle v_2 v_1 v_k ( 3 \leq k \leq n )$ 正好可以覆盖所有的可以取到的角度

所以,只要枚举 $(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 %}

Codeforces 820B.Mister B and Angle in Polygon

题目

题解

代码