判斷圓和矩形是否相交（非面積相交）

判斷圓和矩形是否相交（非面積相交）

月賽題目鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=1165

題解。

問題很簡單，給你一個矩形和一個圓，問你是否他們相交。注意，這裡的相交不是面積相交。也就是說，圓在矩形內（且不相切）是不相交的。或者矩形在圓內（且矩形的四個點不在圓上）也是不相交的。

那麼，我們怎麼來判斷呢？

中間輪廓線是矩形的邊，各向外和內距離為圓半徑r劃線（當然，四個角的肯定不太標准）。

如果圓心在紅色區域的話，肯定是會與圓相交了。。。

當然，如果我們根本畫不出來這種圖形的話。也就是說，可能存在的情況就是圓把矩形給包含在內了，否則的話如果，存在圓心距某一邊的距離小於半徑r的話，必相交。

Code：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const double eps = 1e-8;
const double pi = acos(-1);

struct POINT
{
    double x, y;
    POINT(double a, double b){
        x = a;
        y = b;
    }
    POINT() {}
};

struct Seg
{
    POINT a, b;
    Seg() {}
    Seg(POINT x, POINT y){
        a = x;
        b =y;
    }
};

struct Line
{
    POINT a, b;
    Line() {}
    Line(POINT x, POINT y){
        a = x;
        b = y;
    }
};

struct Cir
{
    POINT o;
    double r;
    Cir() {}
    Cir(POINT oo, double rr){
        o = oo;
        r = rr;
    }
};

struct Rec
{
    POINT p1, p2, p3, p4;
    Rec() { }
    Rec(POINT a, POINT b, POINT c, POINT d){
        p1 = a;
        p2 = b;
        p3 = c;
        p4 = d;
    }
};

int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

double x, y, r;
double x1, yy1, x2, y2;

double cross(POINT o, POINT a, POINT b)
{
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

double dis(POINT a, POINT b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double PointToLine(POINT p, Line l)
{
    return fabs(cross(p, l.a, l.b)) / dis(l.a, l.b);
}

double PointToSeg(POINT p, Seg s)
{
    POINT tmp = p;
    tmp.x += s.a.y - s.b.y;
    tmp.y += s.b.x - s.a.x;
    if(cross(s.a, p, tmp) * cross(s.b, p, tmp) >= eps){
        return min(dis(p, s.a), dis(p, s.b));
    }
    return PointToLine(p, Line(s.a, s.b));
}

//
bool Circle_Rectangle_cross(Cir O, Rec R)
{
    if(dcmp(dis(O.o, R.p1) - O.r) < 0 && dcmp(dis(O.o, R.p2) - O.r) < 0 && dcmp(dis(O.o, R.p3) - O.r) < 0 && dcmp(dis(O.o, R.p4) - O.r) < 0)
        return false;
    if(dcmp(PointToSeg(O.o, Seg(R.p1, R.p2)) - O.r) <= 0) return true;
    if(dcmp(PointToSeg(O.o, Seg(R.p2, R.p3)) - O.r) <= 0) return true;
    if(dcmp(PointToSeg(O.o, Seg(R.p3, R.p4)) - O.r) <= 0) return true;
    if(dcmp(PointToSeg(O.o, Seg(R.p4, R.p1)) - O.r) <= 0) return true;
    return false;
}

int main()
{
//    freopen("1.txt", "r", stdin);
//    freopen("2.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    while(T -- ){
        Cir O;
        Rec R;
        scanf("%lf %lf %lf", &O.o.x, &O.o.y, &O.r);
        scanf("%lf %lf %lf %lf", &R.p1.x, &R.p1.y, &R.p2.x, &R.p2.y);
        scanf("%lf %lf %lf %lf", &R.p3.x, &R.p3.y, &R.p4.x, &R.p4.y);
        if(Circle_Rectangle_cross(O, R)) puts("Yes!");
        else puts("No!");
    }
    return 0;
}