51Nod 圆与三角形

给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出"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示例

Output示例

Yes

No

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.141592653589793238462

#define ios() ios::sync_with_stdio(false)

#define INF 1044266558

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

ll r,n;

struct Node

{

    ll x;

    ll y;

}node[];

ll dist(Node a,Node b)

{

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

bool check(Node a,Node b)

{

    if(((a.y-node[].y)*(a.y-b.y)+(a.x-node[].x)*(a.x-b.x))>=&&((b.y-node[].y)*(b.y-a.y)+(b.x-node[].x)*(b.x-a.x))>=) return true;

    return false;

}

int fun(Node a,Node b)

{

    if(dist(node[],node[])<r*r && dist(node[],node[])<r*r && dist(node[],node[])<r*r) return ;

    else if((dist(node[],node[])<=r*r|| dist(node[],node[])<=r*r || dist(node[],node[])<=r*r) && (dist(node[],node[])>=r*r|| dist(node[],node[])>=r*r || dist(node[],node[])>=r*r)) return ;

    else

    {

        if(((b.y-a.y)*node[].x-node[].y*(b.x-a.x)+b.x*a.y-a.x*b.y)*((b.y-a.y)*node[].x-node[].y*(b.x-a.x)+b.x*a.y-a.x*b.y)>r*r*((b.y-a.y)*(b.y-a.y)+(a.x-b.x)*(a.x-b.x))) return ;

        else if(check(a,b)) return ;

    }

}

int main()

{

    scanf("%lld",&n);

    while(n--)

    {

        scanf("%lld%lld%lld",&node[].x,&node[].y,&r);

        for(int i=;i<=;i++)

            scanf("%lld%lld",&node[i].x,&node[i].y);

        if(fun(node[],node[]) || fun(node[],node[]) || fun(node[],node[])) printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

/*

5

-2 -1 1

1 -2

-1 0

-2 0

0 -1 1

-1 -1

1 1

1 -2

-1 1 1

-2 -2

0 1

-1 -2

-2 -1 1

-1 0

0 0

1 -2

0 -1 1

1 0

1 1

-1 -2

*/

/*

Yes

Yes

Yes

No

Yes

*/

巴特西

51Nod 圆与三角形

最新文章

热门文章