Codeforces 820B.Mister B and Angle in Polygon

274


题目



点击显/隐题目

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 v1 v2 v3$(where $v2$ is the vertex of the angle, and $v1$ and $v3$ lie on its sides) is as close as possible to $a$. In other words, the value $left| angle v1 v2 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) times 180^{circ}$


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

同样,可以证明(数学归纳法)得到 $angle v2 v1 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 )$ 即可


代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论