题目 B. Rolling The Polygon

【题目链接】

按照逆时针绕向给出一个凸多边形的 n 个顶点 P0,P1,··· ,Pn−1，再给出凸多边形内部（含边界） 一点 Q。现在要将这个凸多边形在地上无滑动地滚动一周，初始时 P0P1 边与地面接触，假设当前是 PiP(i+1) mod n 边与地面接触，那么滚动一下之后则是 P(i+1) mod nP(i+2) mod n 边与地面接触。不难发现， 从初始状态滚动 n 下之后 P0P1 边再一次与地面接触，这时认为凸多边形已经滚动了一周。现在你需要 求出凸多边形滚动一周之后点 Q 经过的轨迹长度。

输入格式

第一行包含一个整数 T，表示测试数据的组数。
接下来依次描述 T 组测试数据。对于每组测试数据：
第一行包含一个整数 n，表示凸多边形的顶点数。 接下来 n 行，每行包含两个整数 xPi,yPi，按照逆时针的顺序给出凸多边形 n 个顶点 P1,P2,··· ,Pn 的坐标。
最后一行包含两个整数 xQ,yQ，表示点 Q 的坐标。
保证点 Q 在凸多边形内部（含边界）。

输出格式

对于每组测试数据，输出一行信息 “Case #x: y”（不含引号），其中 x 表示这是第 x 组测试数据， y 表示凸多边形滚动一周之后点 Q 经过的轨迹长度，四舍五入精确到小数点后 3 位，数据保证答案的小 数点后第 4 位不是 4 或 5。

思路

题目说了按照逆时针顺序给出点，每三个点会构成一个角，余弦定理求出角度，然后两点公式求出半径，根据弧长=角度*半径，求出弧长，总弧长即为所求答案，当遍历到最后两个点时，需要结合第一个第二个点，所以把第一第二个点加到第n个点后面。

#include<iostream>
#include<algorithm>
#include<cmath>
#define PI 3.1415926535
using namespace std;
typedef struct node
{
    int x;
    int y;
}Node;
int main()
{
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        int n, tx, ty;
        double ans = 0;
        cin >> n;
        Node que[55];
        for (int i = 0; i < n; i++)
            cin >> que[i].x >> que[i].y;
        que[n] = que[0];
        que[n + 1] = que[1];
        cin >> tx >> ty;
        for (int i = 0; i < n; i++)
        {
            double a, b, c;
            a = sqrt(pow(que[i].x - que[i + 1].x, 2) + pow(que[i].y - que[i + 1].y, 2));
            b = sqrt(pow(que[i + 2].x - que[i + 1].x, 2) + pow(que[i + 2].y - que[i + 1].y, 2));
            c = sqrt(pow(que[i].x - que[i + 2].x, 2) + pow(que[i].y - que[i + 2].y, 2));
            double yuanxinjiao = PI - acos((a*a + b * b - c * c) / (2 * a*b));
            double banjing = sqrt(pow(tx - que[i + 1].x, 2) + pow(ty - que[i + 1].y, 2));
            ans += yuanxinjiao * banjing;
        }
        printf("Case #%d: %.3lf\n", i, ans);
    }
}