广东科技网站建设百度推广技巧方法
题目链接: 点击打开链接
题目大意:给你n个点组成一个凸包并且给你一个圆(圆心半径已知)
求一下几种情况:
- 这n个点不能组成凸包
- 凸包不能包住圆
- 凸包能包住圆
整理了一下多边形的模板
还有用的是一个函数多边形能否包住圆
//判断圆与l1l2组成的线段相不相交,相交返回1
int intersect_seg_circle(point c, double r, point l1, point l2){double t1 = dis(c, l1) - r, t2 = dis(c, l2) - r;point t = c;if (t1<eps || t2<eps)return t1>-eps || t2>-eps;t.x += l1.y - l2.y;t.y += l2.x - l1.x;return xmult(l1, c, t)*xmult(l2, c, t) < eps && disptoline(c, l1, l2) - r < eps;
}//判断圆是否在多边形内
bool circle_in_polygen(double r, point o, int n, point *p)
{for (int i = 1; i < n; i++){bool flag = intersect_seg_circle(o, r, p[i - 1], p[i]);if (flag) { return false; break; }}return true;
}
代码如下:点击打开链接