POJ 1228 Grandpa's Estate 凸包唯一性

题意：给出一个点集，问能否够构成一个稳定凸包，即加入新点后仍然不变。

思路：对凸包的唯一性判断，对任意边判断是否存在三点及三点以上共线，如果有边不满足条件则NO，注意使用水平序，这样一来共线点的包括也较为容易，而极角序对始边和终边的共线问题较为麻烦。

/** @Date    : 2017-07-17 21:08:41

  * @FileName: POJ 1228 稳定凸包.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;

}

////////

int n;

point stk[N];

point p[N];

int cmp(point a, point b)//以p[0]基准 极角序排序

{

	int t = xmult(a, b, p[0]);

	if(t > 0)

		return 1;

	if(t == 0)

		return distc(a, p[0]) < distc(b, p[0]);

	if(t < 0)

		return 0;

}

int cmpC(point a, point b)//水平序排序

{

	return sign(a.x - b.x) < 0 || (sign(a.x - b.x) == 0 && sign(a.y - b.y) < 0);

}

int GrahamA()

{

	double mix, miy;

	mix = miy = 1e10;

	int pos = 0;

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

	{

		if(p[i].y < miy || (p[i].y == miy && p[i].x < mix))

		{

			mix = p[i].x, miy = p[i].y;

			pos = i;

		}

	}

	swap(p[0], p[pos]);

	sort(p + 1, p + n, cmp);

	int top = 0;

	stk[0] = p[0];

	stk[1] = p[1];

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

	{

		while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], p[i])) < 0)

			top--;

		stk[top++] = p[i];

	}

	//stk[++top] = p[0];

	return top;

}

int Graham()//水平序

{

	sort(p, p + n, cmpC);

	int top = 0;

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

	{

		while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], p[i])) < 0)

			top--;

		stk[top++] = p[i];

	}

	int tmp = top;

	for(int i = n - 2; i >= 0; i--)

	{

		while(top > tmp && sign(xmult(stk[top - 2],stk[top - 1] ,p[i] )) < 0)

			top--;

		stk[top++] = p[i];

	}

	if(n > 1)

		top--;

	return top;

}

int check(int m)

{

	//cout << m << endl;

	for(int i = 1; i < m; i++)

	{

		//cout << i << endl;

		//cout << "x:" << stk[i].x << "y:" << stk[i].y << endl;

		//cout << xmult(stk[i - 1], stk[(i + 1)%(m)], stk[i]) << "~" << xmult(stk[i], stk[(i + 2)%(m)], stk[(i + 1)%(m)]) << endl;

		if(sign(xmult(stk[i - 1], stk[(i + 1)%(m)], stk[i])) != 0

			&& sign(xmult(stk[i], stk[(i + 2)%(m)], stk[(i + 1)%(m)])) != 0)

			return 0;

	}

	return 1;

}

/////////

int main()

{

	int T;

	cin >> T;

	while(T--)

	{

		scanf("%d", &n);

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

		{

			double x, y;

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

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

		}

		if(n < 6)

		{

			printf("NO\n");

			continue;

		}

		int cnt = Graham();

		// for(int i = 0 ; i < cnt; i++)

		// 	cout << stk[i].x << "%" << stk[i].y << endl;

		printf("%s\n", check(cnt)?"YES":"NO");

	}

    return 0;

}

巴特西

POJ 1228 Grandpa's Estate 凸包唯一性

最新文章

热门文章

巴特西

POJ 1228 Grandpa's Estate 凸包 唯一性

最新文章

热门文章

POJ 1228 Grandpa's Estate 凸包唯一性