P2644. 令人头疼的物理课

前言：

确实令人头疼啊，没判零卡了我好几个小时，这算是个计算几何的板子吗？

题意及思路：

题意和思路都非常明了，即先对整体求一个最大的凸多边形，再在这个多边形内再求一个凸多边形，那么现在的问题就是如何去求这个多边形。 对于这样一个凸多边形：

经最左边的点和最右边的点连接的线段分割之后就变成了一个上凸包和一个下凸包的组合，所以我们现在只需研究如何求这个上凸包，至于下凸包，旋转过来就是上凸包了。

一、上凸包求法：

首先我们知道上凸包的斜率是不增的，先按横坐标顺序排序，然后从左往右扫，令一个数组q来维护这个上凸包，q里面存的点为目前上凸包所包含的点，那么我们考虑新加入一个点时则有两种情况（分别为图中的点A和点B），如图：

若为点A的情况，D，C，A的斜率递增了，则应该舍弃C点（即将C弹出q），然后再判断A，D和前面的点斜率是否递增，重复此操作，直到A与前面三个点斜率不增为止，然后再将点A加入q中作为上凸包中的一个点。

若为点B的情况，D，C，B斜率不增，B天然符合作为上凸包中的一点，则直接加入即可。

TIPS：对于斜率的比较方法有一个小细节，正常来说我们表示三个点 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ 的斜率不增是用 $\frac {y_1-y_2}{x_1-x_2} \ge \frac {y_2-y_3}{x_2-x_3}$ 来判断，但是这样会出现浮点数影响精度，那么我们只需要把分母乘开就好了。

二、再由一个上凸包和下凸包合并成为一个凸多边形：

这里其实直接将存两个凸包的数组合并成一个就好了，但为什么要拉出来说呢，因为我们在求两个凸包的时候，开头位置和结尾位置会有重复，所以我们应该把重复去掉（注意可能一条竖线上有多个点）。

这样我们就可以 $O(nlogn)$ 的求出一个最大的凸多边形。

三、如何求第一个凸多边形内部的点：

我们发现我们将第一个凸多边形的点排序（记为数组a），再将全部点排序(记为数组b)，则a为b的一个子序列，那么我们只需要单独维护一个指向a的指针，然后扫一遍a即可（其实就是双指针）。

四、如何顶点坐标求面积：

一个高中数学公式： $S = \frac{1}{2}\left|\sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i)\right|$

其中 $(x_{n+1}, y_{n+1}) = (x_1, y_1)$，且点需要按顺时针或逆时针排列。

这样我们就可以 $O(n)$ 的求面积了。

后话：

啊，这样我们就可以 $O(nlogn)$ 的跑完这个题目了，计算几何真难吧。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 4;
int n;
typedef struct Point{
	int x,y;
	bool operator < (const Point& temp) const{
    	if(x != temp.x){
    		return x < temp.x;
    	}
        return y < temp.y;
    }
    bool operator == (const Point& temp) const{
    	return x == temp.x && y == temp.y;
    }
}Point;
bool kcal(Point a,Point b,Point c,bool flag){
	return (a.y - b.y) * (b.x - c.x) >= (b.y - c.y) * (a.x - b.x);
}
vector<Point> point,q1,q2;
vector<Point> process(vector<Point> point1){
	q1.clear(),q2.clear();
	if(point1.size() < 3){
		cout << -1 << endl;
		exit(0);
	}
	sort(point1.begin(),point1.end());
	point1.erase(unique(point1.begin(),point1.end()),point1.end());
	int xx1 = point1[0].x,xx2 = point1[point1.size() - 1].x; 
	for(int i = 0; i < point1.size(); i++){
		int sz = q1.size();
		while(sz >= 2 && !kcal(q1[sz - 2],q1[sz - 1],point1[i],1)){
			q1.pop_back();
			sz--;
		}
		q1.push_back(point1[i]);
	}
	for(int i = point1.size() - 1; i >= 0; i--){
		int sz = q2.size(); 
		while(sz >= 2 && !kcal(q2[sz - 2],q2[sz - 1],point1[i],0)){
			q2.pop_back();
			sz--; 
		}
		q2.push_back(point1[i]);
	}
	int cnt = 0;
	for(int i = 0; i < q1.size(); i++){
		if(q1[i].x == xx2){
			cnt++;
		}
	} 
	while(cnt--)q1.pop_back();
	cnt = 0;
	for(int i = 0; i < q2.size(); i++){
		if(q2[i].x == xx1){
			cnt++;
		}
	}
	while(cnt--)q2.pop_back();
	for(int i = 0; i < q2.size(); i++){
		q1.push_back(q2[i]);
	}
	return q1;
}
int area(vector<Point> temp){
	if(temp.size() < 3)return 0; 
	int sum = 0;
	for(int i = 0; i < temp.size(); i++){
		int j = (i + 1) % temp.size();
		sum += (temp[i].x * temp[j].y - temp[j].x * temp[i].y);
	}
	return abs(sum);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		Point temp;
		cin >> temp.x >> temp.y;
		point.push_back(temp);
	}
	vector<Point> t1 = process(point);
	int S1 = area(t1);
	if(t1.size() < 3){
		cout << -1 << endl;
		return 0;
	}
	vector<Point> temp2;
	sort(point.begin(),point.end());
	point.erase(unique(point.begin(),point.end()),point.end()); 
	sort(t1.begin(),t1.end());
	t1.erase(unique(t1.begin(),t1.end()),t1.end()); 
	int pos = 0;
	for(int i = 0; i < point.size(); i++){
		if(point[i] == t1[pos] && pos < t1.size()){
			pos++;
		}
		else{
			temp2.push_back(point[i]);
		}
	}
	vector<Point> t2 = process(temp2);
	int S2 = area(t2);
	if(t2.size() < 3){
		cout << -1 << endl;
		return 0;
	}
	if(S2 == 0 || S1 == 0){
		cout << -1 << endl;
		return 0;
	}
	cout << S1 - S2 << endl;
}