欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算几何 51nod1298圆与三角形

程序员文章站 2022-04-01 16:52:25
...

挺基础的一道题 就是情况比较多,细节也比较多,代码里有注释

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define emin 1e-10
#define ll long long
#define PI acos(-1.0)
#define N 505
double r;
struct Point
{
	double x,y;
}p[4];
double dis(Point a,Point b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y -b.y );
}
int segOnCircle(Point m,Point n) 
{  //判断线段是否在圆上 ,在圆上返回1 
	double a,b,c,k,d1,d2,a1,a2; //ax+by+c=0
	if(m.x==n.x) a = 1,b= 0,c=-m.x;
	else if(m.y==n.y ) a = 0,b = 1,c = -m.y;
	else{
		a = m.y-n.y ;
		b = n.x -m.x;
		c = m.x*n.y -n.x *m.y ;
	}
	double dis = fabs(a*p[0].x+b*p[0].y+c)/(sqrt(a*a+b*b));//点到直线距离 
	if(dis > r) return 0;
	//判断圆心分别到两个端点构成的角度是否为锐角(前提是两个端点都在圆外 会提前判断的)
	a1 = (p[0].x-m.x )*(n.x-m.x )+(p[0].y-m.y )*(n.y -m.y );
	a2 = (p[0].x-n.x )*(m.x-n.x )+(p[0].y-n.y )*(m.y -n.y ); 
	if(a1>0&&a2>0) return 1; //都是锐角 
	return 0;
}
int intersect()
{
	double disA = dis(p[0],p[1]);
	double disB = dis(p[0],p[2]);
	double disC = dis(p[0],p[3]);
	double R = r*r;
	if(disA<R&&disB<R&&disC<R) return 0;
	else if(disA>R&&disB>R&&disC>R) //就是这里 点全在外边 
		return segOnCircle(p[1],p[2]) || segOnCircle(p[1],p[3]) ||segOnCircle(p[2],p[3]);//全部不相交才返回0 
	return 1; //其余情况 
}
int main()
{
	int t; scanf("%d",&t);
	while(t--){
		scanf("%lf%lf%lf",&p[0].x ,&p[0].y,&r);
		for(int i = 1; i<=3; i++)
			scanf("%lf%lf",&p[i].x,&p[i].y );
		if(intersect()) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
 }