51Nod1298 圆与三角形
程序员文章站
2022-04-01 16:52:55
...
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1298
题意:中文题
解析:首先要分情况讨论,三个点都在园内,那么就是不相交,三个点在圆外,那么问题就变成了圆与线段是否相交的问题了,先求点到直线距离,如果点到直线距离是大于半径的,那么这条直线肯定不相交,否则需要判断,圆心在这条直线上投影的位置,如果在线段外面,则说明圆与线段不相交,如果三条线段都与圆不相交,那么剩下的就是三角形与圆相交了
由于怕精度问题,全部都让他们
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point
{
ll x,y;
point() {}
point(ll _x,ll _y):x(_x),y(_y) {}
point operator - (const point &b)const
{
return point(x-b.x,y-b.y);
}
};
ll d_mul(point p1,point p2)
{
return p1.x*p2.x+p1.y*p2.y;
}
ll dis(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
ll judge(point p1,point p2,point p0,ll r)
{
ll a,b,c; //ax+by+c=0
if(p1.x==p2.x)
a = 1,b = 0,c = -p1.x;
else if(p1.y==p2.y)
a = 0,b = 1,c = -p1.y;
else
{
a = p2.y-p1.y;
b = p1.x-p2.x;
c = p2.x*p1.y-p2.y*p1.x;
}
ll t1 = a*p0.x+b*p0.y+c;
t1 *= t1;
ll t2 = (a*a+b*b)*r*r;
if(t1>t2)
return false;
t1 = d_mul(p0-p1,p2-p1);
t2 = d_mul(p0-p2,p1-p2);
if(t1>0 && t2>0)
return true;
else
return false;
}
bool slove(point a,point b,point c,point p0,ll r)
{
ll d1 = dis(a,p0);
ll d2 = dis(b,p0);
ll d3 = dis(c,p0);
r *= r;
if(d1<r && d2<r && d3<r)
return false;
if(d1>r && d2>r && d3>r)
return judge(a,b,p0,r) || judge(a,c,p0,r) || judge(b,c,p0,r);
return true;
}
int main(void)
{
int t;
cin>>t;
while(t--)
{
point p0,a,b,c;
int r;
cin>>p0.x>>p0.y>>r;
cin>>a.x>>a.y;
cin>>b.x>>b.y;
cin>>c.x>>c.y;
if(slove(a,b,c,p0,r))
puts("Yes");
else
puts("No");
}
return 0;
}