HDOJ 5120-Intersection【几何数学】

╰+攻爆jí腚メ 2022-08-21 08:56 176阅读 0赞

# Intersection #

**Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)**

Total Submission(s): 1857 Accepted Submission(s): 708

Problem Description

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 ≤ 10 5), 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 x i, y i (0 ≤ x i, y i ≤ 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

Source

[2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）][2014ACM_ICPC_-]

解题思路：

求出两个圆环重叠之后的阴影面积，也有可能是两个圆。但是两圆环的重叠面积可以简化成

S=大大+小小-2\*大小。

最后记住这个模板，可以计算整数坐标。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const double pi=acos(-1.0);
    double f(int x1,int x2,int y1,int y2,int r1,int r2)
    {
    	int t;
    	if(r1<r2)
    	{
    		t=r1;
    		r1=r2;
    		r2=t;
    	}
    	double s,l1,l2,s1,s2,s3;
    	double rr;
    	double d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    	rr=(double)(r1+r2);
    	//printf("%lf %lf\n",d,rr);
    	if(d>=rr)
    	{
    		return 0;
    	}
    	else if(d<=(r1-r2))
    	{
    		s=pi*r2*r2;
    	}
    	else 
    	{
    		l1=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
    		l2=acos((r2*r2+d*d-r1*r1)/(2*r2*d));
    		s1=l1*r1*r1;
    		s2=l2*r2*r2;
    		s3=r1*sin(l1)*d;
    		//printf("%lf %lf %lf \n",s1,s2,s3);
    		s=s1+s2-s3;
    	}
    	return s;
    }
    int main()
    {
    	double s1,s2,s3;
    	int t;
    	scanf("%d",&t);
    	int xx=1;
    	while(t--)
    	{
    		int r1,r2;
    		scanf("%d%d",&r1,&r2);
    		int x1,y1,x2,y2;
    		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    		s1=f(x1,x2,y1,y2,r2,r2);
    		s2=f(x1,x2,y1,y2,r2,r1);
    		s3=f(x1,x2,y1,y2,r1,r1);
    		double s=s1+s3-2*s2;
    		//printf("%lf,%lf,%lf\n",s1,s2,s3);
    		printf("Case #%d: ",xx++);
    		//sz
    		printf("%.6lf\n",s);
    	}
    	return 0;
    }

[C556-1009-1.jpg]: /images/20220724/a44edf319d80415aa7123f5d0fb9abc8.png
[C556-1009-2.jpg]: /images/20220724/1597c4fee87a4992a1c267e466914d11.png
[2014ACM_ICPC_-]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014ACM%2FICPC%D1%C7%D6%DE%C7%F8%B1%B1%BE%A9%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B1%B1%CA%A6%BA%CD%C9%CF%BD%BB%A3%A9&source=1&searchmode=source