题解归档 - cf600D

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

• 本地编号：cf600D
• 本地来源：problems/cf600D/idea.md
• 题目链接：https://codeforces.com/contest/600/problem/D
• 原始标题：cf600D — Area of Two Circles' Intersection

思路

cf600D — Area of Two Circles' Intersection

题意

给定两圆心坐标与半径，求交集面积。答案绝对/相对误差 ≤ 1e-6。

做法

设圆心距 d，半径 r1, r2。

1. d ≥ r1 + r2：不相交，面积 0。
2. d ≤ |r1 − r2|：一圆含于另一圆，面积为较小圆面积 π·min(r1,r2)²。
3. 否则部分相交：连心线将交区分成两个弓形。

对圆 1，圆心到公共弦的有向距离（沿连心线）为

a1 = (d² + r1² − r2²) / (2d)，

弓形面积 S(r,a) = r²·arccos(a/r) − a·√(r²−a²)。圆 2 同理得 a2，答案 S(r1,a1)+S(r2,a2)。

等价写法是用圆心角 θ = 2·arccos((d²+r²−R²)/(2dr)) 与扇形减三角形公式 r²(θ−sinθ)/2，两式等价；大坐标下弦长公式更稳。

实现注意

• pi = acos(-1.0)；r 用 long long 输入，几何全用 double。
• 输出 fixed<<setprecision(10) 足够通过 1e-6 判定。
• 对拍：随机坐标/半径，与同一公式的 brute.cpp 比对（WSL 500 组）。

复杂度

O(1)。

代码

来源：problems/cf600D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:17:07
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double pi=acos(-1.0);
double seg(ll r,double a){
    return r*r*acos(a/r)-a*sqrt(r*r-a*a);
}
double area(ll x1,ll y1,ll r1,ll x2,ll y2,ll r2){
    double dx=x1-x2,dy=y1-y2,d=sqrt(dx*dx+dy*dy);
    if(d>=r1+r2) return 0;
    if(d<=fabs(r1-r2)) return pi*min(r1,r2)*min(r1,r2);
    double a1=(d*d+r1*r1-r2*r2)/(2*d);
    double a2=(d*d+r2*r2-r1*r1)/(2*d);
    return seg(r1,a1)+seg(r2,a2);
}
int main(){
    ll x1,y1,r1,x2,y2,r2;
    cin>>x1>>y1>>r1>>x2>>y2>>r2;
    cout<<fixed<<setprecision(10)<<area(x1,y1,r1,x2,y2,r2)<<endl;
    return 0;
}