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

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;
}