HDU-1221 Rectangle and Circle

2016年04月21日 |

acm

| acm 数学题

题目：

Rectangle and Circle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2856 Accepted Submission(s): 705

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

2 1 1 1 1 2 4 3 1 1 1 1 3 4 4.5

Sample Output

YES NO

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>
#include <cmath>
#include <numeric>
#include <algorithm>

using namespace std;

double x, y, r, x_1, y_1, x_2, y_2;
double lx[4];
double ly[4];

inline bool in()
{
    lx[0] = lx[1] = x_1;
    lx[2] = lx[3] = x_2;
    ly[0] = ly[2] = y_1;
    ly[1] = ly[3] = y_2;
    double r2 = r*r;
    int t = 0;
    for (int i = 0;i < 4;++i)
    {
        double l = pow(lx[i] - x, 2) + pow(ly[i] - y, 2);
        if (l == r2)
            return true;
        if (l < r2)
            ++t;
    }
    if (t > 0 && t < 4)
        return true;
    if (t == 4)
        return false;
    if (x >= x_1&&x <= x_2 && min(fabs(y_1 - y), abs(y_2 - y)) <= r)  //1
        return true;                                                  //2
    if (y >= y_1&&y <= y_2 && min(fabs(x_1 - x), abs(x_2 - x)) <= r)  //3
        return true;                                                  //4
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    int T;
    cin >> T;
    while (T--)
    {
        cin >> x >> y >> r >> x_1 >> y_1 >> x_2 >> y_2;
        if (x_1 > x_2)
            swap(x_1, x_2);
        if (y_1 > y_2)
            swap(y_1, y_2);

        if (in())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

解析&吐槽：

这道题只考虑边相交的情况，所以包含是不算 true 的。另外需要注意圆包含矩形的情况。我的代码枚举了四个顶点，记录顶点与圆心距离小于 R 的顶点个数 t:

• 如果有等于 R 的距离，说明有点在圆上，直接 true。
• 如果 t==4，说明矩形在圆内，直接 false。
• t 在 0 到 4 之间时说明既有圆内的顶点也有圆外的顶点，直接 true。
• 然后就剩下 t==0 的情况了。

这时候仍然有可能圆心与矩形边的距离最短，进行判断就可以了。需要注意的是如果矩形在圆内，标号 1-4 一定会判定为 true，所以这种情况要先排除掉。

另外，c++中 abs 和 fabs 是一样的（至少 visual studio 里面是这样），都有针对 double 的重载，所以怎么写都一样啦。