2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest

The 2018/2019 Asia Yinchuan First Round Online Programming

题目大意

一个凸包,凸包上有一个点$G$
在水平面上滚动凸包,问点$G$的滚动轨迹长度是多少.

画一个图

即求弧长$HH’$
显然~$∠ABN=∠HBH’=∠CBI$
那么,求$∠ABN$就相当于求$\pi-∠ABC$
至于$∠ABC$怎么求,就很显然啦.

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)

typedef struct point vec;
struct point { //点的基本数据结构
    double x, y;
    double d;
    point(double _x = 0, double _y = 0)
        : x(_x)
        , y(_y)
    {
    }
    point operator*(const point& i_T) const
    {
        return point(x * i_T.x, y * i_T.y);
    }
    point operator*(double u) const
    {
        return point(x * u, y * u);
    }
    bool operator==(const point& i_T) const
    {
        return x == i_T.x && y == i_T.y;
    }
    point operator/(double u) const
    {
        return point(x / u, y / u);
    }
    point operator+(const point& i_T)
    {
        return point(x + i_T.x, y + i_T.y);
    }
    point operator-(const point& i_T)
    {
        return point(x - i_T.x, y - i_T.y);
    }
    friend bool operator<(point a, point b)
    {
        return a.y == b.y ? a.x < b.x : a.y < b.y;
    }
    friend ostream& operator<<(ostream& out, point& a)
    {
        //cout << a.x << ' ' << a.y;
        printf("%.8f %.8f", a.x, a.y);
        return out;
    }
    friend istream& operator>>(istream& in, point& a)
    {
        in >> a.x >> a.y;
        return in;
    }
} p[100];
double changdu(vec a) //向量长度
{
    return sqrt(a.x * a.x + a.y * a.y);
}
double dianji(vec A, vec B) //点积
{
    return A.x * B.x + A.y * B.y;
}
double jiajiao(vec a, vec b)
{
    return pi - acos(dianji(a,b) / (changdu(a) * changdu(b)));
}
int main()
{
    point p0;
    int n, t, cas = 1;
    scanf("%d", &t);
    for (int k = 1; k <= t; k++) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            cin >> p[i];
        cin >> p0;
        for (int i = 1; i <= n; i++)
            p[i].d = changdu(p0 - p[i]);
        p[0] = p[n], p[n + 1] = p[1];
        double ans = 0;
        for (int i = 1; i <= n; i++)
            ans += p[i].d * jiajiao(p[i - 1]- p[i], p[i + 1]-p[i]);
        printf("Case #%d: %.3f\n", k, ans);
    }
    return 0;
}