题解：P16965 [SCCPC 2026] 星系观测计划

lailai0916 · 2026-08-31 05:11:32 · 题解

题意简述

若干平面点同时绕原点旋转。 所有点的旋转角度始终相同。

每个时刻， 用边平行于坐标轴的最小矩形覆盖所有点。 求该矩形周长的长期平均值。

解题思路

固定一个单位方向向量 u。 所有点在 u 上的投影形成一个区间。 记这个区间的长度为 w(u)。

投影的最大值和最小值都在凸包上取得。 因此，删除凸包内部的点不会改变任何时刻的答案。

先推导凸包周长与投影宽度的关系。

设凸包各条边为 e_i，长度为 l_i。 其方向角记为 \varphi_i。 方向 u 的极角记为 \theta。

沿凸包边界走一周。 投影坐标会从最小值走到最大值， 再从最大值回到最小值。

所以，投影坐标的总变化量是 2w(\theta)。 每条边产生的变化量绝对值为：

将所有边的变化量相加可得：

绝对值余弦在一个整周期内的积分为：

设凸包周长为 L=\sum_i l_i。 对投影宽度积分，得到：

点集旋转 \theta 后， 横向宽度是某一方向上的 w(\theta)。 纵向宽度则对应与它垂直的方向。

因此，最小覆盖矩形的周长为：

平移积分区间不会改变周期函数的整周期积分。 两个宽度项的积分都等于 2L。

于是，一个周期内的平均周长为：

这也说明旋转中心的位置不会影响结果。 最终只需求原点集的凸包周长。

代码使用单调链构造凸包。 先按横坐标和纵坐标排序。 依次维护下凸壳，再反向维护上凸壳。

遇到非逆时针转向时弹出中间点。 这样会去掉凸包边上的多余共线点。

若所有点共线，凸包只保留两个端点。 闭合周长会把端点间的线段计算两次。 此时上面的投影推导仍然成立。

排序决定了总时间复杂度为 O(n\log n)。 空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using ld=long double;
const int N=200005;
const ld pi=acosl(-1);
struct Point
{
    ll x,y;
    Point operator-(const Point &p)const
    {
        return {x-p.x,y-p.y};
    }
    bool operator<(const Point &p)const
    {
        return x<p.x||(x==p.x&&y<p.y);
    }
}a[N],h[N];
ll cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}
ld dis(Point a,Point b)
{
    return hypotl(a.x-b.x,a.y-b.y);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(15);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
        sort(a+1,a+n+1);
        int top=0;
        for(int i=1;i<=n;i++)
        {
            while(top>=2&&cross(h[top]-h[top-1],a[i]-h[top])<=0)top--;
            h[++top]=a[i];
        }
        int k=top;
        for(int i=n-1;i;i--)
        {
            while(top>k&&cross(h[top]-h[top-1],a[i]-h[top])<=0)top--;
            h[++top]=a[i];
        }
        top--;
        ld ans=0;
        for(int i=1;i<=top;i++)ans+=dis(h[i],h[i%top+1]);
        cout<<4*ans/pi<<'\n';
    }
    return 0;
}