题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=1165
周末为小朋友们出一道水题,需要求写一题解,好吧,正好自己也写下题解。
问题很简单,给你一个矩形和一个圆,问你是否他们相交。注意,这里的相交不是面积相交。也就是说,圆在矩形内(且不相切)是不相交的。或者矩形在圆内(且矩形的四个点不在圆上)也是不相交的。
那么,我们怎么来判断呢?
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiclRnblN0LclHdpZXYyd2LcBzNvwVZ2x2bzNXak9CX90TQNNkRrFlQKBTSvwFbslmZvwFMwQzLcVmepNHdu9mZvwFVywUNMZTY18CX052bm9CX90zZNJTTE5UNNRVT4FEVkZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zM5gDNyQjM5EzNyETM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
中间轮廓线是矩形的边,各向外和内距离为圆半径r划线(当然,四个角的肯定不太标准)。
如果圆心在红色区域的话,肯定是会与圆相交了。。。
当然,如果我们根本画不出来这种图形的话。也就是说,可能存在的情况就是圆把矩形给包含在内了,否则的话如果,存在圆心距某一边的距离小于半径r的话,必相交。
Code:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
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;
}
比较简单。。