首页 > 代码库 > 51nod 1298 园与三角形

51nod 1298 园与三角形

2024-11-15 02:08:39   202人阅读

给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出"Yes"，否则输出"No"。（三角形的面积大于0）。

 
技术分享
技术分享
Input
第1行：一个数T，表示输入的测试数量(1 <= T <= 10000)，之后每4行用来描述一组测试数据。
4-1：三个数，前两个数为圆心的坐标xc, yc，第3个数为圆的半径R。(-3000 <= xc, yc <= 3000, 1 <= R <= 3000）
4-2：2个数，三角形第1个点的坐标。
4-3：2个数，三角形第2个点的坐标。
4-4：2个数，三角形第3个点的坐标。(-3000 <= xi, yi <= 3000）
Output
共T行，对于每组输入数据，相交输出"Yes"，否则输出"No"。
Input示例
2
0 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5
Output示例
Yes
No


有三种情况，1、三个点都在园内，肯定不相交，2、三个点都在园外，这时就要判断有没有一条线段与园相交了，3、其他情况都是相交。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #define ll long long
 4 using namespace std;
 5 struct Point{
 6     ll x,y;
 7 };
 8 Point a, b, c;
 9 ll xc, yc, r;
10 ll distance(Point *p1) {
11     return (p1->x-xc)*(p1->x-xc)+(p1->y-yc)*(p1->y-yc);
12 }
13 bool f1() {
14     ll ans1 = distance(&a), ans2 = distance(&b), ans3 = distance(&c);
15     if(ans1 < r*r && ans2 < r*r && ans3 < r*r){
16         printf("No\n");         //三个点都在园内一定是No
17         return false;
18     }else if(ans1 > r*r && ans2 > r*r && ans3 > r*r) return true;   //三个点在园外需要再判断下
19     else {
20         printf("Yes\n");        //其他情况一定是Yes
21         return false;
22     }
23 }
24 bool segOnCircle(Point *p1, Point *p2) {
25     ll a, b, c, dist1, dist2, angle1, angle2;  //ax + by + c = 0
26     if(p1->x == p2->x) {
27         a = 1, b = 0, c = -p1->x;
28     }else if(p1->y == p2->y) {
29         a = 0, b = 1, c = -p1->y;
30     }else {
31         a = p1->y - p2->y;
32         b = p2->x - p1->x;
33         c = p1->x*p2->y - p1->y*p2->x;
34     }
35     dist1 = xc*a + yc*b + c;
36     dist1 *= dist1;
37     dist2 = (a*a + b*b)*r*r;
38     if(dist1 > dist2) return 0;
39     angle1 = (xc - p1->x) * (p2->x - p1->x) + (yc - p1->y) * (p2->y - p1->y);   //向量OA*AB
40     angle2 = (xc - p2->x) * (p1->x - p2->x) + (yc - p2->y) * (p1->y - p2->y);   //向量OB*BA
41     if(angle2 > 0 && angle1 > 0) return true;  //必须两个都大于0才是Yes，具体可以在纸上画下就知道为什么了。
42     else return false;
43 }
44 int main() {
45     int t;
46     cin>>t;
47     while(t--) {
48         cin>>xc>>yc>>r;
49         cin>>a.x>>a.y;
50         cin>>b.x>>b.y;
51         cin>>c.x>>c.y;
52         if(f1()) {
53             if(segOnCircle(&a, &b) || segOnCircle(&b, &c) || segOnCircle(&c, &a)) printf("Yes\n");
54             else printf("No\n");
55         }
56     }
57     return 0;
58 }

 

51nod 1298 园与三角形


联系
我们