首页 > 代码库 > POJ 1584 A Round Peg in a Ground Hole(凸包判定&&圆在凸包内判定)
POJ 1584 A Round Peg in a Ground Hole(凸包判定&&圆在凸包内判定)
博客原文地址:http://blog.csdn.net/xuechelingxiao/article/details/39178777
A Round Peg in a Ground Hole
题目大意:按顺时针或逆时针给出多边形的顶点坐标、圆的半径及圆心坐标。
1.求多边形是否是个凸包,若不是输出“HOLE IS ILL-FORMED”。
2.如果多边形为凸包,判定圆是否在凸包内,若凸包在园内,输出“PEG WILL FIT”,若不在,输出“PEG WILL NOT FIT”。
解题思路:这题大体思路就是用叉积判断一个多边形是不是凸包,因为没告诉给出的点是什么顺序,所以需要判断一下顺时针还是逆时针,还有就是凸包边上的要考虑。
在判断圆是否在凸包内的时候,再用一下叉积,看圆心与凸包叉积是不是一直同号就OK了,再求一下圆心到凸包的每个边的距离是否小于等于圆的半径r(注意这里是小于等于)。 大体上就这些trick,具体见代码吧。
另外放个小福利:WA的同学可以看一下http://midatl.fireduck.com/archive/2003/problems/MidAtlantic-2003/problem-D/
代码如下:
#include <stdio.h> #include <algorithm> #include <math.h> const double eps = 1e-8; using namespace std; struct Point { double x, y; } P[2000], O; struct Line { Point a, b; } ; int dcmp(double x) { return x < -eps ? -1 : x > eps; } double xmult(Point a, Point b, Point c) { return (a.x-c.x)*(b.y-c.y) - (a.y-c.y)*(b.x-c.x); } double Distance(Point a, Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double disptoseg(Point p, Line l){ Point t = p; t.x += l.a.y-l.b.y, t.y += l.b.x-l.a.x; if(xmult(l.a,t,p)*xmult(l.b,t,p)>eps) return Distance(p,l.a) < Distance(p,l.b) ? Distance(p,l.a) : Distance(p,l.b); return fabs(xmult(p, l.a, l.b))/Distance(l.a, l.b); } int main() { int n; double r; while(~scanf("%d", &n) && n >= 3) { scanf("%lf%lf%lf", &r, &O.x, &O.y); for(int i = 0; i < n; ++i) { scanf("%lf%lf", &P[i].x, &P[i].y); } int Max = -2, Min = 2; for(int i = 1; i < n; ++i) { int t = dcmp(xmult(P[i], P[(i+2)%n], P[(i+1)%n])); Max = max(Max, t), Min = min(Min, t); } if(Max+Min != 0) { int flag = 2; for(int i = 0; i < n; ++i) { if(dcmp(disptoseg(O, Line{P[i], P[(i+1)%n]})-r) < 0){ flag--; break; } } for(int i = 0; i < n; ++i) { if(Min == -1){ if(dcmp(xmult(P[(i+1)%n], O, P[i])) != 1) { flag--; break; } } else { if(dcmp(xmult(P[(i+1)%n], O, P[i])) != -1) { flag--; break; } } } if(flag == 2) { printf("PEG WILL FIT\n"); } else { printf("PEG WILL NOT FIT\n"); } } else { printf("HOLE IS ILL-FORMED\n"); } } return 0; }
POJ 1584 A Round Peg in a Ground Hole(凸包判定&&圆在凸包内判定)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。