Intersecting Circles

The equation of a circle with radius r and center is

Write a program that compares two circles to see if they intersect and, if they do, computes the points of intersection. (There can be 1, 2, or and infinite number of such points).

Input

The input to this program will consist of a pair number of lines. Each two lines represent a intersection problem. Each line will contain 3 real numbers constituting the , and r parameters for one circle.

Output

For each problem, the output should be the words "NO INTERSECTION" if the circles do not intersect.

When they have an infinite number of intersection points, the output should be the words "THE CIRCLES ARE THE SAME"

If they do intersect at 1 or 2 points, the output should be a line with one or two pairs, respectively, of real numbers giving the x and y coordinates of any point of intersection. Pairs must be sorted first by their x coordinate and when these are equal by the y coordinate.

Each pair is to be printed in parenthesis with numbers accurately rounded to three digits to the right of the decimal point, as the sample below.

Sample Input

0.0 0.0 1.0 3.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 1.0 1.0 0.0 1.0

Sample Output

NO INTERSECTION THE CIRCLES ARE THE SAME (0.500,-0.866)(0.500,0.866)

交的候，使用旋向量求交。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Cir {
 double x, y, r;
 int scan() {
 return scanf("%lf %lf %lf", &x, &y, &r) == 3;
 }
};
#define eps 1e-6
struct Pt {
 double x, y;
 bool operator<(const Pt other) const {
 if(fabs(x-other.x) < eps)
 return y < other.y;
 return x < other.x;
 }
};
int IntersectCir(Cir A, Cir B, Pt v[]) { // Pt v[] result buffer
 double disAB = sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
 if(fabs(disAB) < eps && fabs(A.r-B.r) < eps) {
 if(A.r < eps) {
 v[0].x = A.x;
 v[0].y = A.y;
 return 1;
 }
 return 0;
 }
 if(A.r+B.r+ps < disAB || A.r+disAB+eps < B.r || B.r+disAB+eps < A.r) {
 return -1;
 }
 double x, y, vx, vy;
 vx = B.x - A.x;
 vy = B.y - A.y;
 if(fabs(disAB-A.r-B.r) < eps || fabs(A.r-disAB-B.r) < eps ||
 fabs(B.r-A.r-disAB) < eps) {
 if(fabs(disAB-A.r-B.r) < eps) { // (A)(B)
 v[0].x = A.x+vx*A.r/(A.r+B.r);
 v[0].y = A.y+vy*A.r/(A.r+B.r);
 } else {
 if(A.r < B.r) { //((A)B)
 v[0].x = A.x-vx*A.r/(B.r-A.r);
 v[0].y = A.y-vy*A.r/(B.r-A.r);
 } else { //((B)A)
 v[0].x = B.x+vx*B.r/(A.r-B.r);
 v[0].y = B.y+vy*B.r/(A.r-B.r);
 }
 }
 return 1;
 }
 double theta = acos((A.r*A.r+disAB*disAB-B.r*B.r)/2/A.r/disAB);
 double rvx, rvy; //rotate vector
 rvx = vx*cos(theta)-vy*sin(theta);
 rvy = vx*sin(theta)+vy*cos(theta);
 v[0].x = A.x+rvx*A.r/disAB;
 v[0].y = A.y+rvy*A.r/disAB;
 rvx = vx*cos(-theta)-vy*sin(-theta);
 rvy = vx*sin(-theta)+vy*cos(-theta);
 v[1].x = A.x+rvx*A.r/disAB;
 v[1].y = A.y+rvy*A.r/disAB;
 return 2;
}
int main() {
 Cir A, B;
#define eps2 5.14e-5
 while(A.scan()) {
 B.scan();
 Pt p[2];
 int r = IntersectCir(A, B, p);
 if(r == 0)
 puts("THE CIRCLES ARE THE SAME");
 else if(r < 0)
 puts("NO INTERSECTION");
 else if(r == 1)
 printf("(%.3lf,%.3lf)\n", p[0].x+eps2, p[0].y+eps2);
 else {
 sort(p, p+2);
 printf("(%.3lf,%.3lf)(%.3lf,%.3lf)\n", p[0].x+eps2, p[0].y+eps2, p[1].x+eps2, p[1].y+eps2);
 }
 }
 return 0;
}
 

您可能以下文章有趣

[UVA][何二分] 295 - Fatman

[UVA][DP] 11151 - Longest Palindrome

[UVA] 10536 - Game of Euler

[UVA][dp] 10201 - Adventures in Moving - Part IV