圓與三角形

1298 圓與三角形 

題目來源： HackerRank

基準時間限制：1 秒 空間限制：131072 KB 分值: 0 難度：基礎題

 收藏

 關注

給出圓的圓心和半徑，以及三角形的三個頂點，問圓同三角形是否相交。相交輸出"Yes"，否則輸出"No"。（三角形的面積大于0）。

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

2
0 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5      

Output示例

Yes
No      

當三個點都在圓的裡面的時候肯定不相交，當三條線段與圓都不與圓相交時三角形與圓也不相交。其他情況相交。

#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define maxn 500000
#define inf 0x3f3f3f
#define ll unsigned long long
#define mod 1000000009
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-8;
struct point{
    double x,y;
    point(){};
    point(double _x,double _y){
        x=_x;y=_y;
    }
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
    double operator *(const point &b)const{
        return x*b.x+y*b.y;
    }
};
int sgn(double x){
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    else return 1;
}
struct line {
    point s,e;
    line(){};
    line(point _s,point _e){
        s=_s;e=_e;
    }
    pair<int,point> operator &(const line &b)const{
        point res=s;
        if(sgn((s-e)^(b.s-b.e))==0){
            if(sgn((s-b.e)^(b.s-b.e))==0)return make_pair(0,res);
            else return make_pair(1,res);
        }
        double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x+=(e.x-s.x)*t;
        res.y+=(e.y-s.y)*t;
        return make_pair(2,res);
    }
};
//bool inter(line l1,line l2){
//    return
//    max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&
//    max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&
//    max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&
//    max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&
//    sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0&&
//    sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0;
//}
double dist(point a,point b){
    return sqrt((a-b)*(a-b));
}
point lis(point p,line l){
    point result;
    double t=((p-l.s)*(l.e-l.s))/((l.e-l.s)*(l.e-l.s));
    if(t>=0&&t<=1){
        result.x=l.s.x+(l.e.x-l.s.x)*t;
        result.y=l.s.y+(l.e.y-l.s.y)*t;
    }
    else {
        if(dist(p,l.s)<dist(p,l.e))
            result =l.s;
        else result=l.e;
    }
    return result;
}
int main(){
    int t;cin>>t;
    while(t--){
    point h;double r;
    point a,b,c;
    cin>>h.x>>h.y>>r;
    cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y;
    if(dist(a,h)<r&&dist(b,h)<r&&dist(c,h)<r)
        cout<<"No"<<endl;
    else if(dist(lis(h,line(a,b)),h)>r&&dist(lis(h,line(a,c)),h)>r&&dist(lis(h,line(c,b)),h)>r)
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
    }
}