UCF Local Programming Contest 2018 J. Circle Meets Square（圆与正方形的位置关系）

We all know that you can’t put a round peg in a square hole. Asking you to do so in this contestwould be cruel and unusual punishment, which is banned by the Eighth Amendment to the UnitedStates Constitution. But, perhaps a more reasonable problem that the Framers of the Constitutionnever thought about is determining if a given circle and square have an intersection of positivearea (overlap), or touch (share a point in common), or don’t touch at all. 

The Framers of the US Constitution and the UCF Programming Team coaches would like to know,given a circle and a square, do the two overlap in some positive area, touch, or don’t touch at all.Help them out by writing a program to solve the problem! 

The Problem:

Given the description of a square and circle in the Cartesian plane, determine if the intersectionbetween the two has positive area (overlap), is a single point (touches) or doesn’t exist.

The Input: 

The first line of input contains three integers: x (-1,000 ≤ x ≤ 1,000), y (-1,000 ≤ x ≤ 1,000), and r(0 < r ≤ 1,000), representing the x and y coordinates and radius, respectively of the circle. 

The second line of input contains three integers: tx (-1,000 ≤ tx < 1,000), ty (-1,000 ≤ ty < 1,000),and s (0 < s ≤ 1,000), where (tx, ty) represents the coordinates of the bottom left corner of the squareand s represents the side length of the square. The square’s top right corner is (tx+s, ty+s), so thatits sides are parallel to the x and y axes. 

The Output: 

If the circle and square don’t touch, output 0 (zero). If they touch at a single point, output 1(one). If they overlap in positive area, output 2 (two). 

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

0 0 5
2 3 1

样例输出1复制

2

样例解释1

样例输入2复制

0 0 5
5 0 6

样例输出2复制

1

样例解释2

样例输入3复制

0 5 4
-1 -1 1

样例输出3复制

0

样例解释3

题意：

若圆与正方形有重叠区域输出2，若相交于一些点输出1，若不相交输出0

思路：

标程：

#include<bits/stdc++.h>
using namespace std;
int x,y,r,tx,ty,s;

int dotInCircle(int a,int b)
{
    if((x-a)*(x-a)+(y-b)*(y-b)<r*r)
        return 1;
    else if ((x-a)*(x-a)+(y-b)*(y-b)==r*r)
        return 2;
    else
        return 0;
}

int dotInSquare(int a,int b)
{
    if(a>tx&&a<tx+s&&b>ty&&b<ty+s)
        return 1;
    else if(a==tx&&b>=ty&&b<=ty+s       
            ||a==tx+s&&b>=ty&&b<=ty+s       
            ||a>=tx&&a<=tx+s&&b==ty       
            ||a>=tx&&a<=tx+s&&b==ty+s)
        return 2;
    else
        return 0;
}

bool overlap()
{
    return dotInCircle(tx,ty)==1         
        ||dotInCircle(tx+s,ty)==1         
        ||dotInCircle(tx,ty+s)==1         
        ||dotInCircle(tx+s,ty+s)==1         
        ||dotInSquare(x,y)==1         
        ||dotInSquare(x+r,y)==1         
        ||dotInSquare(x-r,y)==1         
        ||dotInSquare(x,y+r)==1         
        ||dotInSquare(x,y-r)==1;
}
bool touch()
{
    return dotInCircle(tx,ty)==2         
        ||dotInCircle(tx+s,ty)==2
        ||dotInCircle(tx,ty+s)==2    
        ||dotInCircle(tx+s,ty+s)==2         
        ||dotInSquare(x+r,y)==2         
        ||dotInSquare(x-r,y)==2         
        ||dotInSquare(x,y+r)==2         
        ||dotInSquare(x,y-r)==2;
}
int main()
{
    cin>>x>>y>>r;
    cin>>tx>>ty>>s;
    if(overlap())
        puts("2");
    else if(touch())
        puts("1");
    else
        puts("0");
    return 0;
}

比赛的时候用的圆与线段的位置关系，即分别求出圆心到正方形四条边的距离，和半径相比较（kuangbin模板）：

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const double eps = 1e-18;
const double PI = acos(-1.0);

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;
    }
};

struct Line
{
    Point s, e;
    Line(){};
    Line(Point _s, Point _e)
    {
        s = _s;
        e = _e;
    }
};

double dist(Point a, Point b)
{
    return 1.0 * sqrt((a - b) * (a - b));
}

double nearr(Point P, Line L)   ///点到线段的距离
{
    Point ans;
    double t = 1.0 * ((P - L.s) * (L.e - L.s)) / ((L.e - L.s) * (L.e - L.s));
    if(t >= 0 && t <= 1)
    {
        ans.x = L.s.x + (L.e.x - L.s.x) * t;
        ans.y = L.s.y + (L.e.y - L.s.y) * t;
    }
    else
    {
        if(dist(P, L.s) < dist(P, L.e))
        {
            ans = L.s;
        }
        else
        {
            ans = L.e;
        }
    }
    return 1.0 * dist(ans, P);
}

int main()
{
    double x, y, r, tx, ty, s;
    while(~scanf("%lf%lf%lf%lf%lf%lf", &x, &y, &r, &tx, &ty, &s))
    {
        Point O(x, y);///圆心
        Point A(tx, ty);
        Point B(tx + s, ty);
        Point C(tx, ty + s);
        Point D(tx + s, ty + s);

        ///正方形四条边
        Line L1(A, B);
        Line L2(A, C);
        Line L3(C, D);
        Line L4(B, D);

        double dis1 = nearr(O, L1);
        double dis2 = nearr(O, L2);
        double dis3 = nearr(O, L3);
        double dis4 = nearr(O, L4);

        double minn = min(dis1, min(dis2, min(dis3, dis4)));

        if(tx <= x && x <= tx + s && ty <= y && y <= ty + s)
        {
            cout<<2<<'\n';
            continue;
        }
        if(minn - r < 0)    ///有重叠区域
            cout<<2<<'\n';
        else if(fabs(minn - r) < eps)   ///有共同点
            cout<<1<<'\n';
        else    ///不相交
            cout<<0<<'\n';
    }
    return 0;
}
/*
0 0 5
2 3 1
0 0 5
5 0 6
0 5 4
-1 -1 1
*/