[原创]POJ 2546 Circular Area [相交园面积]【计算几何】

2016-04-08 21:48:50 Tabris_ 阅读数：1281

博客爬取于2020-06-14 22:44:38
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51100090

题目链接：http://poj.org/problem?id=2546

Circular Area
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5662 Accepted: 2215
Description

Your task is to write a program, which, given two circles, calculates the area of their intersection with the accuracy of three digits after decimal point.
Input

In the single line of input file there are space-separated real numbers x1 y1 r1 x2 y2 r2. They represent center coordinates and radii of two circles.
Output

The output file must contain single real number - the area.
Sample Input

20.0 30.0 15.0 40.0 30.0 30.0
Sample Output

608.366

题目大意：
就是求两个圆的相交部分的面积

解题思路：
就是简单的几何题目。
两个圆的位置一共有五种情况
1.内含 2.内切 3.相交 4.外切 5.外离
在计算几何中 内含与内切 可以当做同一种情况 外切与外离 可以当做同一种情况
Ps：如果有疑问可以自己画一画图 就会明白了

所以在计算几何中只要分成3种情况就行了
先定义 d为两圆圆心距离

1.外离
外离

这种情况下d>=r1+r2
两圆间没有相交的部分
所以相交面积是0

2.内含

内含
这种情况下 大圆把小圆全部覆盖
相交的面积就是校园的面积 PI * r1 * r1
此情况下 d<=r大-r小
写成代码就是d <= fabs(r1 - r2)

3.相交
相交

相交的部分可以分成 大小两个圆上弧ab与直线ab围成的图形
即可看作
S扇形abc1-S△abc1+S扇形abc2-S△abc2<=>
S扇形abc1+S扇形abc2-S□ac1bc2;
根据中学学的扇形的面积公式可以推到如下

ang1 = acos((r1 * r1 + d * d - r2 * r2) / 2. / r1 / d)
ang2 = acos((r2 * r2 + d * d - r1 * r1) / 2. / r2 / d)
S扇形abc1=ang1 * r1 * r1
S扇形abc2=ang2 * r2 * r2
S□ac1bc2=d * r1 * sin(ang1)

S = ang1 * r1 * r1+ang2 * r2 * r2 - d * r1 * sin(ang1)

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# include <iostream>
# include <cstdio>
# include <cstring>
# include <cmath>
# include <algorithm>
using namespace std;
# define repf(i,a,b) for(int i=(a);i<=(b);i++)

typedef long long ll;
const double PI = 3.141592653;

struct Round {
    double x, y;
    double r;
} r[2];

double dis(Round a, Round b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double solve(Round a, Round b) {
    double d = dis(a, b);
    if (d >= a.r + b.r)
        return 0;
    if (d <= fabs(a.r - b.r)) {
        double r = a.r < b.r ? a.r : b.r;
        return PI * r * r;
    }
    double ang1 = acos((a.r * a.r + d * d - b.r * b.r) / 2. / a.r / d);
    double ang2 = acos((b.r * b.r + d * d - a.r * a.r) / 2. / b.r / d);
    double ret = ang1 * a.r * a.r + ang2 * b.r * b.r - d * a.r * sin(ang1);
    return ret;
}

int main() {
    while (~scanf("%lf%lf%lf%lf%lf%lf", &r[0].x, &r[0].y, &r[0].r, &r[1].x, &r[1].y, &r[1].r)) {
        printf("%.3f\n", solve(r[0], r[1]));
    }
    return 0;
}