LINK

题意：给出一个多边形，求是否存在核。

思路：比较裸的题，要注意的是求系数和交点时的x和y坐标不要搞混...判断核的顶点数是否大于1就行了

/** @Date    : 2017-07-20 19:55:49

  * @FileName: POJ 3335 半平面交求核.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <algorithm>

#include <utility>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <stack>

#include <queue>

#include <math.h>

//#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

struct point

{

	double x, y;

	point(){}

	point(double _x, double _y){x = _x, y = _y;}

	point operator -(const point &b) const

	{

		return point(x - b.x, y - b.y);

	}

	double operator *(const point &b) const

	{

		return x * b.x + y * b.y;

	}

	double operator ^(const point &b) const

	{

		return x * b.y - y * b.x;

	}

};

double xmult(point p1, point p2, point p0)

{

    return (p1 - p0) ^ (p2 - p0);

}  

double distc(point a, point b)

{

	return sqrt((double)((b - a) * (b - a)));

}

int sign(double x)

{

	if(fabs(x) < eps)

		return 0;

	if(x < 0)

		return -1;

	else

		return 1;

}

//////

point p[N], stk[N], t[N];

//两点确定直线系数

void getlinePara(point x, point y, double &a, double &b, double &c)

{

	a = y.y - x.y;

	b = x.x - y.x;

	c = y.x * x.y - x.x * y.y;

}

void init(int n)//感觉没意义的初始化

{

	for(int i = 0; i < n; i++)

		stk[i] = p[i];

}

point interPoint(point x, point y, double a, double b, double c)

{

	double s = fabs(a * x.x + b * x.y + c);

	double t = fabs(a * y.x + b * y.y + c);

	double xx = (x.x * t + y.x * s) / (s + t);

	double yy = (x.y * t + y.y * s) / (s + t);

	return point(xx, yy);

}

int cut(int n, double a, double b, double c)

{

	int cnt = 0;

	for(int i = 0; i < n; i++)//求所有顶点的划分得到的交点

	{

		if(sign(a * stk[i].x + b * stk[i].y + c) >= 0)

			t[cnt++] = stk[i];

		else {

			if(sign(a*stk[(i-1+n)%n].x + b*stk[(i-1+n)%n].y + c)> 0)

				t[cnt++] = interPoint(stk[i], stk[(i-1+n)%n], a, b, c);

			if(sign(a*stk[(i+1)%n].x + b*stk[(i+1)%n].y + c) > 0)

				t[cnt++] = interPoint(stk[i], stk[(i+1)%n], a, b, c);

		}

	}

	for(int i = 0; i < cnt; i++)//从临时数组取出

		stk[i] = t[i];

	return cnt;//返回核的顶点数

}

int main()

{

	int T;

	cin >> T;

	while(T--)

	{

		int n;

		scanf("%d", &n);

		for(int i = 0; i < n; i++)

		{

			double x, y;

			scanf("%lf%lf", &x, &y);

			p[i] = point(x, y);

		}

		init(n);

		int m = n;

		for(int i = 0; i < n; i++)

		{

			double a, b, c;

			getlinePara(p[i], p[(i + 1)%n], a, b, c);

			m = cut(m, a, b, c);

			//cout << m << endl;

		}

		printf("%s\n", m>0?"YES":"NO");

	}

    return 0;

}