求多边形的核
#include#include #include #define eps 1e-18using namespace std;const int MAXN = 105;double a, b, c;int n, cnt;struct Point{ double x, y;}point[MAXN], p[MAXN], tp[MAXN];void Get_equation(Point p1, Point p2){ a = p2.y - p1.y; b = p1.x - p2.x; c = p2.x * p1.y - p1.x * p2.y;}Point Intersection(Point p1, Point p2){ double u = fabs(a * p1.x + b * p1.y + c); double v = fabs(a * p2.x + b * p2.y + c); Point t; t.x = (p1.x * v + p2.x * u) / (u + v); t.y = (p1.y * v + p2.y * u) / (u + v); return t;}void Cut(){ int tmp = 0; for(int i=1; i<=cnt; i++) { //顺时针是>-eps和>eps，逆时针是 <-eps if(a * p[i].x + b * p[i].y + c > -eps) tp[++tmp] = p[i]; else { if(a * p[i-1].x + b * p[i-1].y + c > eps) tp[++tmp] = Intersection(p[i-1], p[i]); if(a * p[i+1].x + b * p[i+1].y + c > eps) tp[++tmp] = Intersection(p[i], p[i+1]); } } for(int i=1; i<=tmp; i++) p[i] = tp[i]; p[0] = p[tmp]; p[tmp+1] = p[1]; cnt = tmp;}void solve(){ for(int i=1; i<=n; i++) p[i] = point[i]; point[n+1] = point[1]; p[0] = p[n]; p[n+1] = p[1]; cnt = n; for(int i=1; i<=n; i++) { Get_equation(point[i], point[i+1]); Cut(); }}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%lf%lf", &point[i].x, &point[i].y); solve(); puts(cnt > 0? "YES" : "NO"); } return 0;}