HDU 5120 (计算几何+圆相交)

小灰灰 2022-06-07 01:38 140阅读 0赞

问题描述:

Matt is a big fan of logo design. Recently he falls in love with logo made up by rings. The following figures are some famous examples you may know.

![C556-1009-1.jpg][]

A ring is a 2-D figure bounded by two circles sharing the common center. The radius for these circles are denoted by r and R (r < R). For more details, refer to the gray part in the illustration below.  
![C556-1009-2.jpg][]

Matt just designed a new logo consisting of two rings with the same size in the 2-D plane. For his interests, Matt would like to know the area of the intersection of these two rings.

Input

The first line contains only one integer T (T ≤ 105), which indicates the number of test cases. For each test case, the first line contains two integers r, R (0 ≤ r < R ≤ 10).  
  
Each of the following two lines contains two integers xi, yi (0 ≤ xi, yi ≤ 20) indicating the coordinates of the center of each ring.

Output

For each test case, output a single line “Case \#x: y”, where x is the case number (starting from 1) and y is the area of intersection rounded to 6 decimal places.

Sample Input

2
    2 3
    0 0
    0 0
    2 3
    0 0
    5 0

Sample Output

Case #1: 15.707963
    Case #2: 2.250778

题目题意:题目给我们俩个大小相同的圆环，圆心坐标不同，问这个俩个圆环相交的面积是多少。

题目分析:这个题目主要的是要搞清楚圆环有那几种情况（画图不方便![害羞][shy.gif]，我描述一下)

将圆环看出俩个大小圆。

1:俩个圆环的大圆相离

2:俩个圆环的大圆相交，大圆与小圆相离

3:俩个圆环的大圆相交，大圆与小圆相交，小圆与小圆相离

4:俩个圆环的大圆相交，大圆与小圆相交，小圆与小圆相交

5:俩个圆环重合

综上可以得到面积=俩个圆环的大圆相交的面积-一个圆环的大圆与另一个小圆相交的面积\*2（因为对称）+俩个圆环的小圆与小圆相交。

画图可以很直观！

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define PI acos(-1.0)
    using namespace std;
    
    const double eps=1e-9;
    typedef struct node
    {
    	int x;
    	int y;
    	bool operator==(const struct node &a) const {
    	    return x==a.x&&y==a.y;
    	}
    }point;
    double AREA(point a, double r1, point b, double r2)//坐标加半径
    {
    	double d = sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    	if (d >= r1+r2)
    		return 0;
    	if (r1>r2) swap (r1,r2);
    	if(r2 - r1 >= d)
    		return PI*r1*r1;
    	double ang1=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
    	double ang2=acos((r2*r2+d*d-r1*r1)/(2*r2*d));
    	return ang1*r1*r1 + ang2*r2*r2 - r1*d*sin(ang1);
    }
    
    int main()
    {
        int t,icase=1;
        scanf("%d",&t);
        while (t--) {
            point a,b;
            double r,R;
            scanf("%lf%lf",&r,&R);
            scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
            printf("Case #%d: %.6f\n",icase++,AREA(a,R,b,R)-2*AREA(a,R,b,r)+AREA(a,r,b,r));
        }
        return 0;
    }

[C556-1009-1.jpg]: /images/20220607/cb5a64e6973a40bd880ba1d45b6ec478.png
[C556-1009-2.jpg]: /images/20220607/4c5fb37812de488ca4ef6b5d61ef91ab.png
[shy.gif]: /images/20220607/1c29c35aa88143dc92dbd9a263d5ca34.png