【HDU1221】Rectangle and Circle（几何）Rectangle and Circle

89 阅读 0 评论 59 点赞

我是靠谱客的博主无限彩虹，最近开发中收集的这篇文章主要介绍【HDU1221】Rectangle and Circle（几何）Rectangle and Circle，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

Rectangle and Circle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3532 Accepted Submission(s): 930

Problem Description

Given a rectangle and a circle in the coordinate system(two edges of the rectangle are parallel with the X-axis, and the other two are parallel with the Y-axis), you have to tell if their borders intersect.

Note: we call them intersect even if they are just tangent. The circle is located by its centre and radius, and the rectangle is located by one of its diagonal.

Input

The first line of input is a positive integer P which indicates the number of test cases. Then P test cases follow. Each test cases consists of seven real numbers, they are X,Y,R,X1,Y1,X2,Y2. That means the centre of a circle is (X,Y) and the radius of the circle is R, and one of the rectangle's diagonal is (X1,Y1)-(X2,Y2).

Output

For each test case, if the rectangle and the circle intersects, just output "YES" in a single line, or you should output "NO" in a single line.

Sample Input

1 1 1 1 2 4 3

1 1 1 1 3 4 4.5

Sample Output

YES NO

Author

weigang Lee

Source

杭州电子科技大学第三届程序设计大赛

【题意】

判断矩形和圆是否相交。

【解题思路】

只需将圆心到矩形的最大距离lmax与最小距离lmin与圆半径r比较即可。

（1）圆心到矩形的最大距离只可能在矩形的四个顶点取到，所以这个很好做，只需代一下距离公式即可。

（2）圆心到矩形的最小距离为圆心到矩形的边的距离，分以下两种情况。

（3）最后，如果r>lmax || r<lmin都是不能与圆相交的。

【代码】

#include<bits/stdc++.h>
using namespace std;
double f1(double x1,double y1,double x,double y)
{
return sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
}
double f2(double x1,double y1,double x2,double y2,double x,double y)
{
if(x1==x2)
{
if(y<=max(y1,y2) && y>=min(y1,y2))return fabs(x-x1);
double t1=f1(x1,y1,x,y);
double t2=f1(x2,y2,x,y);
return min(t1,t2);
}
if(y1==y2)
{
if(x<=max(x1,x2) && x>=min(x1,x2))return fabs(y-y1);
double t1=f1(x1,y1,x,y);
double t2=f1(x2,y2,x,y);
return min(t1,t2);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
double x,y,r,x1,x2,x3,x4,y1,y2,y3,y4,lmax,lmin;
scanf("%lf%lf%lf%lf%lf%lf%lf",&x,&y,&r,&x1,&y1,&x2,&y2);
x3=x1;y3=y2;x4=x2;y4=y1;
double l1=f1(x1,y1,x,y);
double l2=f1(x2,y2,x,y);
double l3=f1(x3,y3,x,y);
double l4=f1(x4,y4,x,y);
lmax=max(l1,max(l2,max(l3,l4)));
double r1=f2(x1,y1,x3,y3,x,y);
double r2=f2(x1,y1,x4,y4,x,y);
double r3=f2(x2,y2,x3,y3,x,y);
double r4=f2(x2,y2,x4,y4,x,y);
lmin=min(r1,min(r2,min(r3,r4)));
//printf("%f,%fn",lmax,lmin);
if(r<lmin || r>lmax)printf("NOn");
else if(r>=lmin && r<=lmax)printf("YESn");
}
return 0;
}