http://acm.hdu.edu.cn/showproblem.php?pid=1221
1
14 92 31 95 13 96 3
这题只需要判断圆和矩形是否相交，然后在里面是不算相交的。
那么就有好几种情况了。
1、整个矩形在圆形里，NO，（我的做法是所有点到圆心距离小于半径）
2、整个圆在矩形里，NO，一个圆选出5个点，圆心，和最上下左右，如果这些点都在，则不行。我的做法直接PointInPolygon。
3、否则，只要有公共点，就直接YES。然后，如果圆那5个点有一个在矩形，或者矩形的4个点到圆心的距离小于半径，即可。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) #define MY "H:/CodeBlocks/project/CompareTwoFile/DataMy.txt", "w", stdout #define ANS "H:/CodeBlocks/project/CompareTwoFile/DataAns.txt", "w", stdout using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const double eps = 1e-15; bool same(double x, double y) { return fabs(x - y) < eps; } struct coor { double x,y; coor() {} coor(double xx,double yy):x(xx),y(yy) {} double operator ^(coor rhs) const { //计算叉积（向量积），返回数值即可 return x*rhs.y - y*rhs.x; } coor operator -(coor rhs) const { //坐标相减，a-b得到向量ba，返回一个向量（坐标形式） return coor(x-rhs.x,y-rhs.y); } double operator *(coor rhs) const { //数量积，返回数值即可 return x*rhs.x + y*rhs.y; } bool operator ==(coor rhs) const { return same(x,rhs.x)&&same(y,rhs.y); //same的定义其实就是和eps比较 } } a[111], cir[111]; double dis(coor a, coor b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } bool OnSegment (coor a,coor b,coor cmp) { //判断点cmp是否在线段ab上 double min_x = min(a.x,b.x), min_y = min(a.y,b.y); double max_x = max(a.x,b.x), max_y = max(a.y,b.y); if (cmp.x>=min_x && cmp.x<=max_x && cmp.y>=min_y && cmp.y<=max_y) return true; else return false; } int PointInPolygon (coor p[],int n,coor cmp) { int cnt = 0; //记录单侧有多少个交点，这里的p[]，必须有顺序 for (int i=1; i<=n; ++i) { int t = (i+1)>n ? 1:(i+1); //下标为1要这样MOD coor p1=p[i],p2=p[t]; //printf ("%lf %lf %lf %lf*** ",p1.x,p1.y,p2.x,p2.y); if (OnSegment(p1,p2,cmp)) { coor t1 = p1-cmp,t2 = p2-cmp; //同时要叉积等于0，这是在线段上的前提 if ((t1^t2)==0) return 2;// 2表明在多边形上，可以适当省略 } if (cmp.y >= max(p1.y,p2.y)) continue;//交点在延长线上和在凸顶点上的都不要 if (cmp.y < min(p1.y,p2.y)) continue;//交点在凹顶点上就要，这里没取等 if (same(p1.y,p2.y)) continue; //与cmp.y是平行的 double x = (cmp.y-p1.y)*(p1.x-p2.x)/(p1.y-p2.y) + p1.x; //求交点 p1.y != p2.y不会除0 if (x>cmp.x) cnt++;//只统计一侧的交点 } return cnt&1;//0表明点在多边形外，1表明点在多边形内 } void work() { double x, y, R; scanf("%lf%lf%lf", &x, &y, &R); double xx1, xx2, yy1, yy2; scanf("%lf%lf%lf%lf", &xx1, &yy1, &xx2, &yy2); int lena = 0; a[++lena] = coor(xx1, yy1); a[++lena] = coor(xx1, yy2); a[++lena] = coor(xx2, yy2); a[++lena] = coor(xx2, yy1); int lencir = 0; cir[++lencir] = coor(x + R, y); cir[++lencir] = coor(x, y + R); cir[++lencir] = coor(x - R, y); cir[++lencir] = coor(x, y - R); cir[++lencir] = coor(x, y); int up = 0; for (int i = 1; i <= lencir; ++i) { if (PointInPolygon(a, 4, cir[i])) { up++; } if (PointInPolygon(a, 4, cir[i]) == 2 && i != lencir) { printf("YES "); return; } } if (up == lencir) { printf("NO "); return; } up = 0; for (int i = 1; i <= lena; ++i) { double tdis = dis(a[i], coor(x, y)); if (same(tdis, R)) { printf("YES "); return; } if (tdis < R) up++; } if (up == lena) { printf("NO "); return; } for (int i = 1; i <= lena; ++i) { double tdis = dis(a[i], coor(x, y)); if (same(tdis, R) || tdis < R) { printf("YES "); return; } } for (int i = 1; i <= lencir; ++i) { if (PointInPolygon(a, 4, cir[i])) { printf("YES "); return; } } printf("NO "); // cout << dis(coor(5,5), coor(7, 7)) << endl; return; } int main() { #ifdef local freopen("data.txt","r",stdin); freopen(MY); #endif int t; scanf("%d", &t); while (t--) { work(); } return 0; }
开始的时候，判断有一个点在就行的时候，（就是相切的时候），把圆心也算进去了，坑了半天。
https://www.desmos.com/calculator 分享个画图工具，矩形的话，就直接是x>=10 x <= 99这样画