[codevs 3273] 两圆的交

题解

需要考虑几种情况：

外切或外离。面积为0，注意要输出 0.000。内切或内含或重合。面积为较小圆的面积。相交，还需要讨论交点位置： 交点在两圆心中间 即异侧交点在两圆心同侧

在求三角形面积的时候有两种方法：

运用三角形两边的叉积的绝对值的1/2计算。运用海伦公式计算。

不过我试了所有方法仍然有一个点WA了，，已经用while(1)实验出问题是出在交点在两圆心同侧的情况了。可能是精度问题。

后来学到了一种更为简单的方法，第二种代码给出的。推导见注释。

代码：

2ms，256kB 90 分 （WA一点）

;struct Point {double x, y;Point(double x=0, double y=0):x(x),y(y) {}}p1, p2;typedef Point Vector;Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }Vector operator – (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); }Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }bool operator < (const Vector& a, const Vector& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}const double eps = 1e-10;int dcmp(double x) {x < 0 ? -1 : 1;}double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }double Length(Vector A) { return sqrt(Dot(A, A)); }double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }double Cross(Vector A, Vector B) { return A.x*B.y – A.y*B.x; }double Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); }bool operator == (const Vector& a, const Vector& b) {return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;}const double PI = acos(double(-1));struct Circle {Point c;double r;Point point(double a) {return Point(c.x + cos(a)*r, c.y + sin(a)*r);}double S() { return PI*r*r; }}C1, C2;double angle(Vector v) { return atan2(v.y, v.x); }int getCircleCircleIntersection() {double d = Length(C1.c – C2.c);if(dcmp(d) == 0) {if(dcmp(C1.r-C2.r) == 0) return -1;return 0;}if(dcmp(C1.r+C2.r-d) < 0) return 0;if(dcmp(fabs(C1.r-C2.r)-d > 0)) return 0;double a = angle(C2.c-C1.c);double da = acos((C1.r*C1.r + d*d – C2.r*C2.r) / (2*C1.r*d));p1 = C1.point(a-da), p2 = C1.point(a+da);return p1 == p2 ? 1 : 2;}double Area(double a, double b, double c) {double p = (a+b+c) / 2.0;return sqrt(p*(p-a)*(p-b)*(p-c));}int main() {cin >> C1.c.x >> C1.c.y >> C1.r >> C2.c.x >> C2.c.y >> C2.r;int c = getCircleCircleIntersection();double d = sqrt((C1.c.x-C2.c.x)*(C1.c.x-C2.c.x) + (C1.c.y-C2.c.y)*(C1.c.y-C2.c.y));; }//内含或内切或重合if(dcmp(max(C1.r, C2.r)-min(C1.r, C2.r)-d) >= 0) {printf(“%.3lf\n”, min(C1.r, C2.r)*min(C1.r, C2.r)*PI);return 0;}//相交Vector v1, v2;d = Length(p1-p2);v1 = p1-C1.c, v2 = p2-C1.c;double s11 = Area(Length(v1), Length(v2), Length(d)), s12 = C1.r*C1.r*Angle(v1, v2) / 2;v1 = p1-C2.c, v2 = p2-C2.c;double s21 = Area(Length(v1), Length(v2), Length(d)), s22 = C2.r*C2.r*Angle(v1, v2) / 2;//讨论交点位置if(dcmp(C1.c.x-p1.x) * dcmp(C2.c.x-p1.x) <= 0)printf(“%.3lf\n”, s12+s22 – s11-s21);else {if(C1.r > C2.r) printf(“%.3lf\n”, C2.S() + s21 – s22 – s11 + s12);else printf(“%.3lf\n”, C1.S() + s11 – s12 – s21 + s22); //WA}return 0;}

更为简单的方法： 10ms，256 kB

;int main() {const double pi = acos(double(-1));double x1, y1, r1, x2, y2, r2;scanf(“%lf%lf%lf%lf%lf%lf”, &x1, &y1, &r1, &x2, &y2, &r2);; } ; } n = p = r2*r2*pi*(asin(n/r2)/pi) – n*fabs(d-m);if(m > d) p = r2*r2*pi – p; //画图推导一下。printf(“%.3lf\n”, o + p);return 0;}

一个人骑行，孤单却内省;一群人骑行，壮观而有力。