题解归档 - cf613A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf613A
• 本地来源：problems/cf613A/idea.md
• 题目链接：https://codeforces.com/contest/613/problem/A
• 原始标题：CF613A — Peter and Snow Blower

思路

CF613A — Peter and Snow Blower

题意

多边形绕形外一点 (P) 旋转一周，求扫过区域面积。

关键观察

(P) 严格在多边形外时，从 (P) 看各点到 (P) 的距离在边界上连续变化，扫过区域是圆环：

[
\text{Area} = \pi (R^2 - r^2)
]

• (R)：(P) 到任意顶点的最远距离（最远点必在顶点）。
• (r)：(P) 到任意边的最短距离（垂足可能落在线段内部，需做点–线段距离）。

凹多边形同样成立；(r) 不能只用顶点距离。

点–线段距离

对边 (AB) 与点 (P)：投影在 (A) 外侧 → (|PA|)；在 (B) 外侧 → (|PB|)；否则为 (P) 到直线 (AB) 的垂距。

复杂度

(O(n))。

样例

• 样例 1：(r=1)，(R=\sqrt5) → (4\pi)。
• 样例 2：(r=\sqrt2)，(R=3) → (7\pi)。

调试

• 首次提交 RE：改用 double + sqrt 实现点–线段距离（避免 hypotl/long double 在远端编译器上的兼容问题）。
• 对拍 200 组通过（Kali 不可达时用 WSL 验证）。

参考

• 官方题解

代码

来源：problems/cf613A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 06:15:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
const double pi=acos(-1.0);
ll x[maxn+5],y[maxn+5];
double dis2(ll x1,ll y1,ll x2,ll y2){
    double dx=x1-x2,dy=y1-y2;
    return sqrt(dx*dx+dy*dy);
}
double dist(ll x1,ll y1,ll x2,ll y2,ll px,ll py){
    double dx=x2-x1,dy=y2-y1;
    double fx=px-x1,fy=py-y1;
    double sl=dx*dx+dy*dy;
    double dot=fx*dx+fy*dy;
    if(dot<=0) return dis2(px,py,x1,y1);
    if(dot>=sl) return dis2(px,py,x2,y2);
    double cross=fx*dy-fy*dx;
    if(cross<0) cross=-cross;
    return cross/sqrt(sl);
}
int main(){
    ll n,i,j,px,py;
    double mn,mx,cur;
    cin>>n>>px>>py;
    mn=1e18;
    mx=0;
    for(i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        cur=dis2(x[i],y[i],px,py);
        if(cur<mn) mn=cur;
        if(cur>mx) mx=cur;
    }
    for(i=1;i<=n;i++){
        j=i%n+1;
        cur=dist(x[i],y[i],x[j],y[j],px,py);
        if(cur<mn) mn=cur;
    }
    cout<<fixed<<setprecision(15)<<(mx*mx-mn*mn)*pi<<endl;
    return 0;
}