金牌导航 凸包-稳定凸包

【题解】金牌导航-凸包-稳定凸包

题面：

做法详解：

考虑一个什么样的凸包是一个稳定的凸包（推荐自己画画图，就理解了）
若对于凸包上的每一条边，都有包含其端点在内至少三个不同位置的点，那么这就肯定是一个稳定的凸包。
考虑若只有两个点，那么在其外面在加入一个点，那么这个点与其对应的这条边可以同时被计算入新的凸包
考虑若有三个及更多的点，那么在其外面加入一个点，这条边上除了两个端点之外的那些点就不可能再计入新的凸包里了，所以这就是一个稳定的凸包
实现起来非常好搞：对于每一条凸包上的边统计有多少个点在这条边上，注意这些点不一定要是凸包上的点
小细节：
（1）可能会有重复的点，那么这样的点肯定不能被算多次，所以要去重
（2）考虑若凸包就是一条线，那么肯定不会是一个稳定的凸包，因为在其延长线上再随意找一个点也可以形成一个包含所有点的新凸包

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+4;
struct V{
	int x,y;
	V(int _x = 0 ,int _y = 0){
		x = _x,y = _y;
	}
}q[MAXN],a[MAXN],tmp[MAXN];
int head,n;
V operator - (V l,V r){
	return V(l.x - r.x,l.y - r.y);
}
int operator * (V l,V r){
	return l.x * r.y - l.y * r.x;
}
int dot(V l,V r){
	return l.x * r.x + l.y * r.y;
}
int len(V l){
	return sqrt(l.x * l.x + l.y * l.y);
}
bool cmp(V l,V r){
	V u = (l - a[1]),w = (r - a[1]);
	int h = u * w;
	if(h != 0){
		return h > 0;
	}
	if(l.x != r.x)
		return l.x < r.x;
	return l.y<r.y;
}
bool cmp_x(V l,V r){
	if(l.x != r.x)
		return l.x < r.x;
	return l.y < r.y;
}
void Graham(){
	int pos = 1;
	for(int i=2; i<=n; i++){
		if(a[i].x < a[pos].x || (a[i].x == a[pos].x && a[i].y < a[pos].y)){
			pos = i;
		}
	}
	if(pos != 1){
		swap(a[pos],a[1]);
	}
	sort(a+2,a+n+1,cmp);
	for(int i=1; i<=n; i++){
		while(head >= 2 && (a[i] - q[head -1]) * (q[head] - q[head - 1]) >= 0){
			head--;
		}
		q[++head] = a[i];
	}
	q[head + 1] = q[1];
}
bool in_line(V p,V from,V to){
	int h = (from - p) * (to - p);
	if(h != 0)
		return false;
	return dot((from - p),(to - p)) <= 0;
}
bool check_ans(V from,V to){
	int res = 0;
	for(int i=1; i<=n; i++){
		if(in_line(a[i],from,to))
			res++;
		if(res >= 3)
			return true;
	}
	return res >= 3;
}
int cross(V x,V y,V z){
	return (y - x) * (z - x);
}
int Area(){
	int res = 0;
	for(int i=1; i<=head; i++){
		res += q[i] * q[i+1];
	}
	return res;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		head = 0;
		int h;
		cin>>h;
		for(int i=1; i<=h; i++){
			cin>>tmp[i].x>>tmp[i].y;
		}
		sort(tmp+1,tmp+h+1,cmp_x);
		a[1] = tmp[1];
		n = 1;
		for(int i=2; i<=h; i++){
			if(tmp[i].x != tmp[i-1].x || tmp[i].y != tmp[i-1].y)
				a[++n] = tmp[i];
		}
		Graham();
		bool flag = false;
		for(int i=1; i<=head; i++){
			if(!check_ans(q[i],q[i+1])){
				printf("NO\n");
				flag = true;
				break;
			}
		}
		if(Area() == 0 && !flag){
			printf("NO\n");
		}
		else if(!flag){
			printf("YES\n");
		}
	}
	return 0;
}