1298 圆与三角形(计算几何)

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示例

1
2
3
4
5
6
7
8
9
2
0 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5

Output示例

1
2
Yes
No

题解:

判断圆和三角形是否相交 直接判断三角形三条线段和圆是否有交点 上个计算几何模版

最初的思路是分成三种情况考虑 一种是内包含 只要判断三个点是否都在圆内即可 第二种是外包含 要判断三个点都在圆外且圆心到三边距离都大于半径 第三种是下图情况 就不好操作了 所以还是直接用模版啦

然后系统说我编译错误 明明sublime编译通过了的 麻烦诶。。然后用devc++试了下 报了下图的错

查了是因为distance和内置的函数重名了 改改就好了下次注意

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <list>
#include <vector>
using namespace std;

#define eps 1e-8
double a0,b0,r,a1,a2,a3,b1,b2,b3;
struct point{
double x,y;
}q0,q1,q2,q3;
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Distance(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
// 点到直线距离
double disptoline(point p,point l1,point l2){
return fabs(xmult(p,l1,l2)/Distance(l1,l2));
}
// 判断线段和圆相交,包括端点和相切(p33)
int intersect_seg_circle(point c,double r0,point l1,point l2){
double t1=Distance(c,l1)-r,t2=Distance(c,l2)-r;
point t=c;
if(t1<eps||t2<eps)return t1>-eps||t2>-eps;
t.x+=l1.y-l2.y;
t.y+=l2.x-l1.x;
return xmult(l1,c,t)*xmult(l2,c,t)<eps&&disptoline(c,l1,l2)-r<eps;
}
bool check(){
if(intersect_seg_circle(q0,r,q1,q2))return true;
if(intersect_seg_circle(q0,r,q1,q3))return true;
if(intersect_seg_circle(q0,r,q2,q3))return true;
return false;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lf%lf%lf",&a0,&b0,&r);q0.x=a0;q0.y=b0;
scanf("%lf%lf",&a1,&b1);q1.x=a1;q1.y=b1;
scanf("%lf%lf",&a2,&b2);q2.x=a2;q2.y=b2;
scanf("%lf%lf",&a3,&b3);q3.x=a3;q3.y=b3;
if(check())puts("Yes");
else puts("No");
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信