POJ 3335 Rotating Scoreboard 半平面交求核

题意：给出一个多边形，求是否存在核。
思路：比较裸的题，要注意的是求系数和交点时的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
", m>0?"YES":"NO");
	}
    return 0;
}
POJ 3335 Rotating Scoreboard 半平面交求核

相关推荐
