L. 分煎饼
知识点：计算几何、二分
直接计算能平分所有圆的直线的方程比较困难，但是给定一条直线，分别计算两侧的圆的面积和是相对容易的。
一条直线可以用两个参数确定，考虑固定住直线的一个参数，在调整另一个参数的过程中，如果直线两边的面积是单调变化的，就可以使用二分来解决这个问题。
举个例子，可以固定斜率为零，二分截距。
当然还有很多种二分的方法，出题人试过以下几种，都轻松通过了，没有出现精度问题。
- 固定方向为水平或垂直，二分与原点的距离
- 随机一个方向，二分与原点的距离
- 固定经过原点，二分倾斜角
考虑如何根据一条给定的直线计算一个圆在直线两侧的面积。
如图所示，设圆的半径为 ，圆心距直线的距离为
（有正负）。
如果 或
，则两侧的面积很好计算。
否则，直线上方的面积可以用扇形 ACD 的面积（记为 ）减去三角形 ACD 的面积（记为
）表示。
设
则有 
是有正负的）
是有正负的）
我们要求的面积为
这样计算并不需要分类讨论直线在圆心的上方还是下方。
标程
C++
正常写法：固定方向水平，二分与原点的距离
#include <bits/stdc++.h>
using namespace std;
constexpr double pi = 3.14159265358979323846;
struct Circle
{
int x, y, r;
};
pair<double, double> split(double r, double d)
{
double S = r * r * pi;
if (d >= r)
{
return {0.0, S};
}
if (d <= -r)
{
return {S, 0.0};
}
double theta = acos(d / r);
double A = r * r * theta - d * sqrt(r * r - d * d);
return {A, S - A};
}
pair<double, double> check(const vector<Circle> &a, double y)
{
double S1 = 0.0, S2 = 0.0;
for (const Circle &c : a)
{
double d = y - c.y;
auto [s1, s2] = split(c.r, d);
S1 += s1;
S2 += s2;
}
return {S1, S2};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(ios::fixed);
cout.precision(18);
int n;
cin >> n;
vector<Circle> a(n);
double S = 0.0;
for (auto &[x, y, r] : a)
{
cin >> x >> y >> r;
S += r * r * pi;
}
double l = 0, r = 1e4, mid;
while (true)
{
mid = (l + r) / 2;
auto [S1, S2] = check(a, mid);
if (fabs(S1 - S2) <= 1e-9 * S)
{
break;
}
if (S1 > S2)
{
l = mid;
}
else
{
r = mid;
}
}
double A = 0.0, B = 1.0, C = -mid;
cout << A << '\n'
<< B << '\n'
<< C << '\n';
}
整活写法：随机一个方向，二分与原点的距离
#include <bits/stdc++.h>
using namespace std;
constexpr double pi = 3.14159265358979323846;
struct Circle
{
double x, y, r;
};
pair<double, double> split(double r, double d)
{
double S = r * r * pi;
if (d >= r)
{
return {0.0, S};
}
if (d <= -r)
{
return {S, 0.0};
}
double theta = acos(d / r);
double A = r * r * theta - d * sqrt(r * r - d * d);
return {A, S - A};
}
pair<double, double> check(const vector<Circle> &a, double y)
{
double S1 = 0.0, S2 = 0.0;
for (const Circle &c : a)
{
double d = y - c.y;
auto [s1, s2] = split(c.r, d);
S1 += s1;
S2 += s2;
}
return {S1, S2};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(ios::fixed);
cout.precision(18);
int n;
cin >> n;
vector<Circle> a(n);
double S = 0.0;
for (auto &c : a)
{
int x, y, r;
cin >> x >> y >> r;
c.x = x;
c.y = y;
c.r = r;
S += r * r * pi;
}
mt19937 rng(19260817);
double theta = uniform_real_distribution<double>(0, 2 * pi)(rng);
for (auto &c : a)
{
double x = c.x * cos(theta) - c.y * sin(theta);
double y = c.x * sin(theta) + c.y * cos(theta);
c.x = x;
c.y = y;
}
double l = -1e5, r = 1e5, mid;
while (true)
{
mid = (l + r) / 2;
auto [S1, S2] = check(a, mid);
if (fabs(S1 - S2) <= 1e-9 * S)
{
break;
}
if (S1 > S2)
{
l = mid;
}
else
{
r = mid;
}
}
double A = sin(theta), B = cos(theta), C = -mid;
cout << A << '\n'
<< B << '\n'
<< C << '\n';
}
Java
import java.util.*;
import java.io.*;
public class Main {
static Kattio io = new Kattio();
static int n;
static int[] x, y, r;
static double split(double r, double d) {
if (d >= r) {
return 0;
}
if (d <= -r) {
return r * r * Math.PI;
}
double theta = Math.acos(d / r);
return r * r * theta - d * Math.sqrt(r * r - d * d);
}
static double check(double b) { // y = b
double res = 0;
for (int i = 0; i < n; i++) {
double d = b - y[i];
res += split(r[i], d);
}
return res;
}
public static void main(String[] args) {
n = io.nextInt();
x = new int[n];
y = new int[n];
r = new int[n];
double S = 0;
for (int i = 0; i < n; i++) {
x[i] = io.nextInt();
y[i] = io.nextInt();
r[i] = io.nextInt();
S += r[i] * r[i] * Math.PI;
}
double l = 0, r = 1e4, mid;
while (true) {
mid = (l + r) / 2;
double res = check(mid);
double S1 = res, S2 = S - res;
if (Math.abs(S1 - S2) <= 1e-9 * S) {
break;
}
if (S1 > S2) {
l = mid;
} else {
r = mid;
}
}
double A = 0.0, B = 1.0, C = -mid; // y = mid
io.printf("%.18f\n", A);
io.printf("%.18f\n", B);
io.printf("%.18f\n", C);
io.close();
}
}
class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// 标准 IO
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// 在没有其他输入时返回 null
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) {}
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
Python
固定经过原点，二分倾斜角
import math
def split(r: float, d: float):
S = r * r * math.pi
if d >= r:
return 0.0, S
if d <= -r:
return S, 0.0
theta = math.acos(d / r)
A = r * r * theta - d * math.sqrt(r * r - d * d)
return A, S - A
def check(A: float, B: float, C: float):
S1, S2 = 0.0, 0.0
for x, y, r in circles:
# d 表示圆心到直线的距离（有向）
# 这里省略了除法，因此需要保证 A^2 + B^2 = 1
d = A * x + B * y + C
s1, s2 = split(r, d)
S1 += s1
S2 += s2
return S1, S2
n = int(input())
circles = []
S = 0.0
for i in range(n):
x, y, r = map(float, input().split())
circles.append((x, y, r))
S += r * r * math.pi
l, r = 0, math.pi / 2
while True:
theta = (l + r) / 2
# 与 x 轴的夹角为 theta 的直线
A = math.sin(theta)
B = -math.cos(theta)
C = 0.0
S1, S2 = check(A, B, C)
if abs(S1 - S2) < 1e-9 * S:
break
if S1 > S2:
l = theta
else:
r = theta
print(f"{A:.18f}")
print(f"{B:.18f}")
print(f"{C:.18f}")
京公网安备 11010502036488号