FJNU 1151 Fat Brother And Geometry（胖哥与几何）

Time Limit: 1000MS Memory Limit: 257792K

【Description】

【题目描述】

Fat brother enrolled in computer graphics, recently teacher arranged a job: given two straight lines and a circle, judge if the round is between straight two lines. If it is, fat brother need to submit a “Yes” to the teacher. If not, fat brother need to submit “No” to the teacher.

Note:

Straight line will be expressed through two point in it

Circle will be expressed through a center point and a radius

胖哥选修了计算机图形学，最近老师给他布置了个任务：给定两条直线与一个圆，判断这个圆是否在两条直线中。如果是，提交“Yes”给老师。否则，胖哥需要提交“No”给老师。

注意：

直线以两点表示。

圆以圆心和半径表示。

【Input】

【输入】

There are multiple test cases. The first line of input contains an integer T (T <= 20) indicating the number of test cases. For each test case:

The first line contains four number Ax1, Ay1, Ax2, Ay2 denoting there are two point (Ax1, Ay1), (Ax2, Ay2) on the line A

The second line contains four number Bx1, By1, Bx2, By2 denoting there are two point (Bx1, By1), (Bx2, By2) on the line B

The third line contains three number Ox, Oy, r denoting the center of the circle O is (Ox, Oy) and the radius of the circle O is r

( -10^9 <= x, y, r <= 10 ^ 9)

多组测试用例。

第一行是一个整数T(T <= 20)表示测试用例的数量。对于每个测试用例：

第一行有四个数Ax1, Ay1, Ax2, Ay2表示直线A上的两点(Ax1, Ay1), (Ax2, Ay2)。

第二行有四个数Bx1, By1, Bx2, By2表示直线A上的两点(Bx1, By1), (Bx2, By2)。

第行有三个数Ox, Oy, r表示圆心O的坐标(Ox, Oy)和圆O的半径为r。

( -10^9 <= x, y, r <= 10 ^ 9)

【Output】	【输出】
For each test case, output “Yes” or “No”	对于测试用例，输出“Yes”或“No”。

【Sample Input - 输入样例】

【Sample Output - 输出样例】

-5.98 5.98 -8.52 2.01

-2.01 4.97 -6.03 -1.06

-6.96 3.94 1.03

-19.98 11.93 19.95 -2.01

16.01 11.93 -17.97 -12.12

12.04 3.92 2.09

Yes

【Hint - 提示】

测试用例一

The first sample test case:

测试用例二

The second sample test case:

【题解】

大意是判断圆和直线的关系，不过输入数据是double类型。

由于浮点数的精度，最容易发生问题的地方是在两个数比较是否相等的时候，此时应该算上最低的精度，不过题目也没说精度是多少……按之前看过的类似题目就去10e-8好了。

（一开始条件反射在考虑如何用ax+by+c>0直接判断……想了想发觉没什么卵用）

按直线的位置划分情况：

①两条直线相交：圆心到直线的距离是否大于半径。

②两条直线平行：两条平行线的距离是否大于直径。

接着就是两点式化一般式。

得：(y₁- y₂)x + (x₂- x₁)y + x₁y₂-x₂y₁ = 0

因此：a = y₁- y₂，b = x₂- x₁，c = x₁y₂-x₂y₁

点到直线的距离：

平行线间的距离：

不过两条直线的a，b不定各自相等，转化一下就好了。

之后就没啥好说的了。

【代码 C++】

 1 #include<cstdio>
 2 #include <cmath>
 3 #define Zero 10e-8
 4 int main(){
 5     int t, n;
 6     double x1, y1, x2, y2, a1, b1, c1, a2, b2, c2, r, L1, L2;
 7     while (~scanf("%d", &t)){
 8         while (t--){
 9             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
10             a1 = y1 - y2; b1 = x2 - x1; c1 = x1*y2 - x2*y1;
11             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
12             a2 = y1 - y2; b2 = x2 - x1; c2 = x1*y2 - x2*y1;
13             scanf("%lf%lf%lf", &x1, &y1, &r);
14             L1 = fabs(a1*x1 + b1*y1 + c1) / sqrt(a1*a1 + b1*b1);
15             L2 = fabs(a2*x1 + b2*y1 + c2) / sqrt(a2*a2 + b2*b2);
16             if (L1 < r) puts("No");
17             else if (L2 < r) puts("No");
18             else if (fabs(a1*b2 - a2*b1) > Zero) puts("Yes");
19             else if (fabs(fabs(c1 - c2 / (a2 + b2)*(a1 + b1)) / sqrt(a1*a1 + b1*b1) - L1 - L2) > Zero) puts("No");
20             else puts("Yes");
21         }
22     }
23     return 0;
24 }