LightOJ 1118--Incredible Molecules(两圆相交)
LightOJ 1118--Incredible Molecules(两圆相交)
1118 - Incredible Molecules PDF (English) Statistics Forum Time Limit: 0.5 second(s) Memory Limit: 32 MB In the biological lab, you were examining some of the molecules. You got some interesting behavior about some of the molecules. There are some circular molecules, when two of them collide, they overlap with each other, and it’s hard to find that which one is over the other one.
Given two molecules as circles, you have to find the common area of the given molecules that is shaded in the picture.
Overlapping Molecules
Input Input starts with an integer T(≤12)T(≤12)T(≤12)T (≤ 12), denoting the number of test cases.
Each case contains six integers x1,y1,r1x1,y1,r1x1,y1,r1x1, y1, r1 and x2,y2,r2x2,y2,r2x2,y2,r2x2, y2, r2. Where(x1,y1)(x1,y1)(x1,y1) (x1, y1) is the center of the first molecule and r1r1r1r1 is the radius and (x2,y2)(x2,y2)(x2,y2)(x2, y2)is the center of the second molecule and r2 is the radius. Both the radiuses are positive. No integer will contain more than 3 digits.
Output For each test case, print the case number and the common area of the given molecules. Errors less than 10-6 will be ignored.
Sample Input Output for Sample Input 3
0 0 10 15 0 10
-10 -10 5 0 -10 10
100 100 20 100 110 20
Case 1: 45.3311753978
Case 2: 35.07666099 首先，判断两圆关系，如果相交(两个交点)，则求出相交的面积，外离和外切相交面积为0.
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const double PI = acos(-1.0);
typedef struct point {
double x;
double y;
point() {
}
point(double a, double b) {
x = a;
y = b;
}
friend istream& operator >> (istream& in, point&b) {
in >> b.x >> b.y;
return in;
}
point operator -(const point &b)const {
return point(x - b.x, y - b.y);
}
point operator +(const point &b)const {
return point(x + b.x, y + b.y);
}
point operator *(const double &k)const {
return point(x * k, y * k);
}
point operator /(const double &k)const {
return point(x / k, y / k);
}
double operator ^(const point &b)const {
return x*b.y - y*b.x;
}
double operator *(const point &b)const {
return x*b.x + y*b.y;
}
}point;
typedef struct circle {
double r;
point centre;
friend istream& operator >> (istream &in, circle &b) {
in >> b.centre >> b.r;
return in;
}
double area() {
return PI*r*r;
}
}circle;
double dist(point p1, point p2) {
return sqrt((p1 - p2)*(p1 - p2));
}
void CircleInterArea(circle a, circle b, double &s1, double &s2) {//相交面积
double d = dist(a.centre, b.centre);//圆心距
double t = (d*d + a.r*a.r - b.r*b.r) / (2.0 * d);//
double h = sqrt((a.r*a.r) - (t*t)) * 2;//h1=h2
double angle_a = 2 * acos((a.r*a.r + d*d - b.r*b.r) / (2.0 * a.r*d));
//余弦公式计算r1对应圆心角，弧度
double angle_b = 2 * acos((b.r*b.r + d*d - a.r*a.r) / (2.0 * b.r*d));
//余弦公式计算r2对应圆心角，弧度
double la = angle_a*a.r;//r1所对应的相交弧长
double lb = angle_b*b.r;//r2所对应的相交弧长
s1 = la*a.r / 2.0 - a.r*a.r*sin(angle_a) / 2.0; //相交部分r1圆的面积
s2 = lb*b.r / 2.0 - b.r*b.r*sin(angle_b) / 2.0; //相交部分r2圆的面积
//double rest_s1 = PI*a.r*a.r - s1 - s2;//r1圆剩余部分面积，不含相交部分面积
//double rest_s2 = PI*b.r*b.r - s1 - s2;//r1圆剩余部分面积，不含相交部分面积
}
//两圆关系
int CircleInterNum(circle a, circle b) {
double fh = fabs(a.r + b.r), fc = fabs(a.r - b.r), d = dist(a.centre, b.centre);
if (d>fh)
return -2; //外离,没有交点
if (d == fh)
return -1; //外切，一个交点
if (d > fc&&d < fh)
return 0; //相交，两个交点
if (d == fc)
return 1; //内切，一个交点
if (d < fc&&d >= 0)
return 2; //内含，没有交点
}
int main(void) {
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
circle c1, c2;
double s1, s2;
cin >> c1 >> c2;
int f = CircleInterNum(c1, c2);
if (f == 0) {
CircleInterArea(c1, c2, s1, s2);
printf("Case %d: %.8f\n", i, s1 + s2);
}
else if (f == -2 || f == -1) {
printf("Case %d: 0\n", i);
}
else if (f == 1 || f == 2) {
printf("Case %d: %.8f\n", i,min(c1.area(),c2.area()));
}
}
return 0;
}