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

Tabris

CSDNPOJ计算几何

发布于：2016年4月8日

次浏览

[原创]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)

附本题代码

# 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;  
}