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.
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.
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.
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.
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.
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
容斥原理很明显，圆交的求法是我自己想的，很简单。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namespace std; 6 int T,cas,r,R,px,py,qx,qy; 7 const double Pi=acos(-1.0); 8 double sqr(double x){return x*x;} 9 double Q(double r1,double r2){ 10 double d=sqrt(sqr(px-qx)+sqr(py-qy)); 11 if(r1+r2<=d)return 0; 12 if(r1-r2>=d)return Pi*sqr(r2); 13 double a1=acos((sqr(r1)+sqr(d)-sqr(r2))/(2*r1*d)); 14 double a2=acos((sqr(r2)+sqr(d)-sqr(r1))/(2*r2*d)); 15 double s1=sqr(r1)*a1; 16 double s2=sqr(r2)*a2; 17 return s1+s2-r1*sin(a1)*d; 18 } 19 int main(){ 20 scanf("%d",&T); 21 while(T--){ 22 scanf("%d%d",&r,&R); 23 scanf("%d%d%d%d",&px,&py,&qx,&qy); 24 printf("Case #%d: %.6lf ",++cas,Q(R,R)-2*Q(R,r)+Q(r,r)); 25 } 26 return 0; 27 }