POJ - 3335 Rotating Scoreboard（半平面交判断多边形内核）

本文主要是介绍POJ - 3335 Rotating Scoreboard（半平面交判断多边形内核），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接 Rotating Scoreboard

题意

顺时针给出一些点，判断这些点构成的多边形是否存在内核；

思路

多边形内核：
它是平面简单多边形的核是该多边形内部的一个点集，该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。就是一个在一个房子里面放一个摄像头，能将所有的地方监视到的放摄像头的地点的集合即为多边形的核。
在这里插入图片描述

利用半平面交，最后判断队列里的点是否 $> 2$ 即可；

AC代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>#define x first
#define y secondusing namespace std;const double eps = 1e-8;
const int N = 10010;
typedef pair<double, double> PDD;
const double pi = 3.1415926535898;int T;
int n, cnt;
PDD p[N];
int q[N];struct Line
{PDD st, ed;
} line[N];PDD operator -(PDD a, PDD b)
{return make_pair(a.x - b.x, a.y - b.y);
}int sign(double x)
{if (fabs(x) < eps) return 0;if (x < 0) return -1;return 1;
}int dcmp(double x, double y)
{if (fabs(x - y) < eps) return 0;if (x < y) return -1;return 1;
}double cross(PDD a, PDD b)
{return a.x * b.y - a.y * b.x;
}double area(PDD a, PDD b, PDD c)
{return cross(b - a, c - a);
}PDD get_intersect(PDD p, PDD v, PDD q, PDD w)
{PDD u = p - q;double t = cross(w, u) / cross(v, w);return make_pair(p.x + v.x * t, p.y + v.y * t);
}double point_product(PDD a, PDD b)
{return a.x * b.x + a.y * b.y;
}double get_len(PDD a, PDD b)
{double dx = a.x - b.x;double dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}double get_angle(Line a)
{return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}bool cmp(Line a, Line b)
{double A = get_angle(a);double B = get_angle(b);if (!dcmp(A, B)) return area(a.st, a.ed, b.st) < 0;return A < B;
}PDD get_intersect(Line a, Line b)
{return get_intersect(a.st, a.ed - a.st, b.st, b.ed - b.st);
}bool on_right(Line a, Line b, Line c)
{PDD o = get_intersect(b, c);return sign(area(a.st, a.ed, o)) < 0;
}bool half_plane_intersection()
{sort(line, line + cnt, cmp);int hh = 0, tt = -1;for (int i = 0; i < cnt; i ++){if (i && !dcmp(get_angle(line[i]), get_angle(line[i - 1]))) continue;while (hh + 1 <= tt && on_right(line[i], line[q[tt]], line[q[tt - 1]])) tt --;while (hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh ++;q[++ tt] = i;}while (hh + 1 <= tt && on_right(line[q[hh]], line[q[tt]], line[q[tt - 1]])) tt --;while (hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++;q[++ tt] = q[hh];return tt - hh >= 3;
}int main()
{cin >> T;while (T --){cin >> n;cnt = 0;for (int i = 0; i < n; i ++) cin >> p[i].x >> p[i].y;//顺时针变成逆时针for (int i = 0; i < n / 2; i ++) swap(p[i], p[n - i - 1]);//for (int i = 0; i < n; i ++) cout << "****" << p[i].x << " " << p[i].y << endl;for (int i = 0; i < n; i ++){line[cnt].st = p[i];line[cnt ++].ed =  p[(i + 1) % n];}bool flag = half_plane_intersection();if (flag) puts("YES");else puts("NO");}
}