51nod 1298圆与三角形（判断线段与圆相交）

题目

给三角形三个点，圆心，半径，问三角形圆是否相交？

分析

1. 三点在圆内，不相交
2. 三点在圆外，要考虑判断,下文分析
3. 剩下的情况都相交

三点在圆外时，只需判断三条线段是否与圆相交，若有一条相交，输出Yes

转化为线段与圆相交，在端点都在圆外情况下。

推导线段所在直线方程：
线段所在直线方程的一般式为：ax+by+c=0;线段两个端点A（x1,y1),B(x2,y2);圆心O(px,py),根据y=kx+z;那么直线斜率k=y1-y2/x1-x2;然后再将点A带入方程可得z=(x1y2-x2y1)/(x1-x2),然后转化成一般式的形式则：
a=y1-y2,b=x2x1,c=x1y2-x2y1。

判断圆心到线段所在直线距离，只能小于半径。

然后用余弦定理判断圆心与两端点角度是否为锐角。

代码

#include <bits/stdc++.h>
#pragma GCC diagnostic error "-std=c++11"
#define d(x) cout << (x) << endl
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 14;

struct point
{
    double x, y;
    point(){
        scanf("%lf%lf", &x, &y);
    }
};

double dis(point a, point b)    //距离平方
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int seg_cir(point p1, point p2, point cir, double r)    //线段相交圆（两端点在圆外）
{
    double a, b, c, dis1, dis2, angle1, angle2;
    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 = p1.y - p2.y;
        b = p2.x - p1.x;
        c = p1.x * p2.y - p1.y * p2.x;
    }
    dis1 = a * cir.x + b * cir.y + c;
    dis1 *= dis1;
    dis2 = (a * a + b * b) * r * r;
    if (dis1 > dis2)    return 0;
    angle1 = (cir.x - p1.x) * (p2.x - p1.x) + (cir.y - p1.y) * (p2.y - p1.y);
    angle2 = (cir.x - p2.x) * (p1.x - p2.x) + (cir.y - p2.y) * (p1.y - p2.y);
    if (angle1 > 0 && angle2 > 0)   return 1;   //正弦大于零为锐角
    return 0;
}
int solve()
{
    double r;
    point cir;
    scanf("%lf", &r);
    point a, b, c;
    double dis1 = dis(cir, a);
    double dis2 = dis(cir, b);
    double dis3 = dis(cir, c);
    double rr = r * r;
    if(dis1 < rr && dis2 < rr && dis3 < rr){    //三点在圆内
        return 0;
    }else if(dis1 > rr && dis2 > rr && dis3 > rr){  //三点在圆外
        return seg_cir(a, b, cir, r) || seg_cir(b, c, cir, r) || seg_cir(a, c, cir, r);
    }
    return 1;
}
int main()
{
    int t;
    for (cin >> t; t; t--){
        cout << (solve() ? "Yes" : "No") << endl;
    }
    return 0;
}