板题大赏。

板题1 凸包

我们先选最左下的一个点，它一定在凸包上。

于是将其他的点按照与左下点的极角排序，用单调队列维护外凸即可。（因为凸包的外边按照顺序一定是极角依次增大）

（p.s 对于此题，在一条线上的点不会影响最后答案，可以不用在极角的基础上按照长度排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int M=1e5+5;
const double eps=1e-9;
inline int sig(double x){
	if(fabs(x)<eps) return 0;
	else return x>0?1:-1;
}
struct point{
	double x,y;
	point(double _x=0.0,double _y=0.0){
		x=_x,y=_y;
	}
	point operator - (point r){
		return point(r.x-x,r.y-y);
	}
	double operator ^ (point r){
		return x*r.y-y*r.x;
	}
}p[M];
int id=1;
inline bool cmp(point a,point b){
	if(sig((p[1]-a)^(p[1]-b))>0) return 1;
    //对于此题，在一条线上的点不会影响最后答案，可以不用按照长度排序
	return 0;
}
int sta[M];
double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	id=1;
	for(int i=2;i<=n;i++){
		if(p[i].x<p[id].x) id=i;
		else if(p[i].x==p[id].x&&p[i].y<p[id].y) id=i;
	}swap(p[1],p[id]);
	sort(p+2,p+n+1,cmp);
	int h=1,t=2;sta[1]=1;sta[2]=2;
	for(int i=3;i<=n;i++){
		while(t>1&&((p[sta[t-1]]-p[sta[t]])^(p[sta[t]]-p[i]))<0) t--;
		sta[++t]=i; 
	}
	sta[++t]=1;double ans=0;
	for(int i=1;i<t;i++){
		ans+=dis(p[sta[i]],p[sta[i+1]]);
	}
	printf("%0.2lf",ans);
	return 0;
}

板题2 旋转卡壳

求最远点对。

显而易见最远点对一定在凸包上。于是考虑在凸包上如何求解。

我们随便选一条边，枚举得出这条边的最远点（可以用叉积面积快速判断），按照逆时针枚举边，注意到最优点的位置也是顺时针变化，于是枚举完一遍边的同时，最优点对也只会旋转一圈。

（p.s 注意这里所有点可能在一条直线上，所以排序时按照极角+长度排序，去凸包时自动只保留最远两点）

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int M=1e5+5;
const double eps=1e-9;
inline int sig(double x){
	if(!x) return 0;
	else return x>0?1:-1;
}
struct point{
	int x,y;
	point(int _x=0.0,int _y=0.0){
		x=_x,y=_y;
	}
	point operator - (point r){
		return point(r.x-x,r.y-y);
	}
	double operator ^ (point r){
		return x*r.y-y*r.x;
	}
	int operator * (point r){
		return x*r.x+y*r.y;
	}
}p[M];
int id=1;
double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int disdis(point a,point b){
	return ((a.x-b.x)*(a.x-b.x)+((a.y-b.y)*(a.y-b.y)));
}
inline bool cmp(point a,point b){
	if(sig((p[1]-a)^(p[1]-b))>0) return 1;
	else if(!sig((p[1]-a)^(p[1]-b)))  if(disdis(p[1],a)<disdis(p[1],b)) return 1;
	return 0;
}
int sta[M];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
	id=1;
	for(int i=2;i<=n;i++){
		if(p[i].x<p[id].x) id=i;
		else if(p[i].x==p[id].x&&p[i].y<p[id].y) id=i;
	}swap(p[1],p[id]);
	sort(p+2,p+n+1,cmp);
	int h=1,t=2;sta[1]=1;sta[2]=2;
	for(int i=3;i<=n;i++){
		while(t>1&&((p[sta[t-1]]-p[sta[t]])^(p[sta[t-1]]-p[i]))<=0) t--;
		sta[++t]=i; 
	}
	if(t==2){
		cout<<disdis(p[sta[1]],p[sta[2]])<<endl;return 0;
	}
	int j=3;sta[++t]=1;int ans=0;
	for(int i=1;i<t;i++){
		while(((p[sta[i]]-p[sta[i+1]])^(p[sta[i+1]]-p[sta[j]]))<((p[sta[i]]-p[sta[i+1]])^(p[sta[i+1]]-p[sta[j+1]]))) if(j==t) j=1;else j++;
		ans=max(ans,max(disdis(p[sta[i]],p[sta[j]]),disdis(p[sta[i+1]],p[sta[j]])));
	}
	cout<<ans<<endl;
	return 0;
}

板题3 半平面交

基本流程如下：

  1. 把所有边按照极角排序

  2. 排序时如果极角相同，我们保留最右的边（默认有效半平面为左边）

  3. 排序后按照极角从小到大枚举边，与当前单调队列的队首队尾点和次队首队尾点合并，如果可以完全替代则替代掉。（单调队列基本操作）

  4. 结束后不要忘记对最后的单调队列首尾各来一次判断（因为你单调队列只保证了一段最优）

  5. 我们得到了构成最后面积交的线段（且是按极角排序后的），于是一一算出交点即可。

  6. 最后根据交点套面积公式即可

一点补充：

  1. 如果三条边中，两条边交点在第三边合法侧，那么第三边会被覆盖，可以删去。

  2. 因为极角本身是圆，故每次按极角大小加入一条新边时，对队首队尾都可能有威胁，于是从两个方向删边即可。

  3. 注意加完边后，我们只保证了从第一条边到最后一条边连续的边不会被删掉，但是这只是线形的（有可能新加的边本身就是废边，但是这条废边也许会因为后来加的都是废边而不被删掉），于是再把头和尾做一次删边。

  4. 如果实现时把上一个交点在线上也t–（保证精度），那么就要保证最后从头从尾删数时保证h<t−1h<t-1（保证判断的三条线段不会有相等）/*循环里还是h<th<t

  5. 数据过大要用long doublelong \ double,否则就会像我这样调一下午。

  6. 最后记得特判掉总点数小于3的情况，否则会输出non且不会报错。（其实死咬住求交点时除数不为0即可（即直线不平行））

  7. 保证如果有解一定是封闭图形（如果图形不封闭，我们就要人为加上边界线）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int M=1000;
const double eps=1e-10;
inline int sig(double x){
	if(fabs(x)<eps) return 0;
	return x>0?1:-1;
}
struct point{
	double x,y;
	point(double _x=0.0,double _y=0.0){
		x=_x,y=_y;
	}
	point operator - (point r){
		return point(r.x-x,r.y-y);
	}
	double operator ^ (point r){
		return x*r.y-y*r.x;
	}
	point operator * (double k){
		return point(x*k,y*k);
	}
	point operator + (point r){
		return point(x+r.x,y+r.y);
	}
}p[M],fin[M];
struct line{
	point s,t;double val;
	line(point a=point(0.0,0.0),point b=point(0.0,0.0)){
		s=a,t=b;
	}
}l[M];
inline bool cmp(line l,line r){
	if(l.val<r.val) return 1;
	if(!sig(l.val-r.val)) if(sig((l.s-l.t)^(l.s-r.t))>0) return 1;
	return 0; 
}
int tot,sta[M];
point pointcross(line aa,line bb){
	point a=aa.s,b=aa.t,c=bb.s,d=bb.t;
	double S1=(a-d)^(d-c),S2=(c-d)^(a-b);
	return a+(a-b)*(S1/S2);
}
inline bool check(line a,line b,line c){
	point jiao=pointcross(a,b);
	return sig((c.s-c.t)^(c.s-jiao))<0;
}
signed main(){
	int N;cin>>N;
	while(N--){
		cin>>n;
		for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
		p[++n]=p[1];
		for(int i=1;i<n;i++) l[++tot]=line(p[i],p[i+1]),l[tot].val=atan2(p[i+1].y-p[i].y,p[i+1].x-p[i].x);
	}
	sort(l+1,l+tot+1,cmp);int tot1=0;
	for(int i=1;i<=tot;i++){
		if(sig(l[i].val-l[i-1].val)!=0) tot1++;l[tot1]=l[i];
	}tot=tot1;
	int h=1,t=0;
	for(int i=1;i<=tot;i++){
		while(h<t&&check(l[sta[t]],l[sta[t-1]],l[i])) t--;
		while(h<t&&check(l[sta[h]],l[sta[h+1]],l[i])) h++;
		sta[++t]=i;
	}
	while(h<t-1&&check(l[sta[t]],l[sta[t-1]],l[sta[h]])) t--;
	while(h<t-1&&check(l[sta[h]],l[sta[h+1]],l[sta[t]])) h++;
   if(t-h+1<3){
      cout<<"0.000";return 0;
   }
	sta[++t]=sta[h];int cnt1=0;
	for(int i=h;i<t;i++) fin[++cnt1]=pointcross(l[sta[i]],l[sta[i+1]]);fin[++cnt1]=fin[1];
	double ans=0.0;
	for(int i=1;i<cnt1;i++) ans+=fin[i]^fin[i+1];
	ans=fabs(ans)/2;
	printf("%0.3lf",ans);
	return 0;
}

板题口糊完了，看几道简单的例题

例题1 [SCOI2007]最大土地面积

四边形在凸包上

对于一个四边形，我们枚举对角线，假设我们已经确定了一条对角线，那么现在的目的即是找到对角线两侧最大三角形面积，由于是凸包，显然两侧的点到对角线距离是单峰，于是貌似三分可以做大O(N2logN)O(N^2logN)貌似可以过了。

继续考虑优化，我们枚举a，再枚举b，假设a-b就是对角线，于是在枚举b的时候，两侧的最远点也是按顺序转动，于是单调队列维护即可。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//我也不知道为什么之前写计算几何代码这么丑
#include<bits/stdc++.h>
using namespace std;
const int M=1e4;
const double eps=0.00000001;
int n,m;
struct point{
	double x,y;
}p[M],sta[M]; 
inline point getvec(point a,point b){
	point v;v.x=b.x-a.x,v.y=b.y-a.y;
	return v;
}
inline double mulx(point a,point b){
	return a.x*b.y-a.y*b.x;
}
inline double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline bool cmp(point a,point b){
	double tmp=mulx(getvec(p[1],a),getvec(p[1],b));
	if(tmp>0) return 1;
	if(fabs(tmp)<=eps&&dis(p[1],a)<dis(p[1],b)) return 1;
	return 0; 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&p[i].x,&p[i].y);
		if(i!=1){
			if(p[i].x<p[1].x) swap(p[1],p[i]);
			if(fabs(p[i].x-p[1].x)<=eps&&p[1].y>p[i].y) swap(p[1],p[i]);
		}
	}
	sort(p+2,p+n+1,cmp);
	double ans=0;int cnt=0;
	sta[++cnt]=p[1];
	for(int i=2;i<=n;i++){
		while(cnt>1&&mulx(getvec(sta[cnt-1],sta[cnt]),getvec(sta[cnt-1],p[i]))<=0) cnt--;
		sta[++cnt]=p[i];
	}
	m=cnt;
//	for(int i=1;i<=m;i++) cout<<sta[i].x<<" "<<sta[i].y<<endl;
	for(int i=1;i<=m;i++){
		int a=i%m+1,b=(i+2)%m+1;
		for(int j=(i+1)%m+1;j<=m;j++){
			while(a%m+1!=j&&fabs(mulx(getvec(sta[i],sta[a]),getvec(sta[i],sta[j])))<fabs(mulx(getvec(sta[i],sta[a%m+1]),getvec(sta[i],sta[j])))) a=a%m+1;
			while(b%m+1!=i&&fabs(mulx(getvec(sta[i],sta[b]),getvec(sta[i],sta[j])))<fabs(mulx(getvec(sta[i],sta[b%m+1]),getvec(sta[i],sta[j])))) b=b%m+1;
			ans=max(ans,fabs(mulx(getvec(sta[i],sta[a]),getvec(sta[i],sta[j])))+fabs(mulx(getvec(sta[i],sta[b]),getvec(sta[i],sta[j]))));
		//	cout<<ans<<endl;
		}
	}
	printf("%0.3lf",ans/2);
	return 0;
}

例题2 [CQOI2005]三角形面积并

扫描线求解面积并。

我们算出每一个交点，那么扫描线停留在这些交点的x坐标上，而相邻两条扫描线的贡献是，扫描线的距离乘上扫描线的中位线截所有三角形的长度的并。

暴力搞出来就好了。

时间复杂度 O(N3)O(N^3)

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=500;
const double eps=1e-9,inf=1e7;
struct point{
	double x,y;
	point(double xx=0.0,double yy=0.0){
		x=xx,y=yy;
	}
	point operator - (point r){
		return point(r.x-x,r.y-y);
	}
	double operator ^ (point r){
		return x*r.y-y*r.x;
	}
	point operator + (point r){
		return point(x+r.x,y+r.y);
	}
	point operator * (double k){
		return point(x*k,y*k);
	}
}p[M][5],seg[M];
inline bool cmp(point a,point b){
	return a.x<b.x;
}
double ans,px[M*M];
int n,m;
inline int sig(double x){
	if(fabs(x)<eps) return 0;
	return x>0?1:-1;
}
inline bool ifcross(point a,point b,point c,point d){
	int d1=sig((a-b)^(a-d)),d2=sig((a-b)^(a-c));
	int d3=sig((d-c)^(d-b)),d4=sig((d-c)^(d-a));
	return (d1*d2<0)&&(d3*d4<0);
}
inline point pointcross(point a,point b,point p,point q){
	double S1=((a-p)^(p-q)),S2=(a-b)^(p-q);
	return a+(a-b)*fabs(S1/S2);
}
inline double scan(double x){
	point D(x,-inf),U(x,inf);
	int cnt=0,cnt1=0;
	for(int i=0;i<n;i++){
	    cnt=0;double y[2];
		for(int j=0;j<3;j++){	
			if(ifcross(p[i][j],p[i][j+1],D,U)){
				y[cnt++]=pointcross(p[i][j],p[i][j+1],D,U).y;
			}
		}if(cnt) seg[++cnt1]=point(min(y[0],y[1]),max(y[0],y[1]));
	}
	if(cnt1>=2) sort(seg+1,seg+cnt1+1,cmp);
	double l=-inf,r=-inf,sum=0.0;
	for(int i=1;i<=cnt1;i++){
		//cout<<seg[i].x<<"^"<<seg[i].y<<endl;
		if(sig(seg[i].x-r)>0) sum+=r-l,l=seg[i].x;
		r=max(r,seg[i].y);
	}//cout<<x<<"="<<sum<<"&";cout<<sum<<endl;
	sum+=r-l;
	return sum;
}
signed main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++) cin>>p[i][j].x>>p[i][j].y;
		p[i][3]=p[i][0];
	}int cnt1=0;
	for(int i=0;i<n;i++) for(int j=0;j<3;j++) px[++cnt1]=p[i][j].x;
	for(int i=0;i<n;i++)
	  for(int j=i+1;j<n;j++)
	    for(int k=0;k<3;k++)
	      for(int l=0;l<3;l++){
	      	if(ifcross(p[i][k],p[i][k+1],p[j][l],p[j][l+1])){
	      		px[++cnt1]=pointcross(p[i][k],p[i][k+1],p[j][l],p[j][l+1]).x;
	      	}
	      }
	sort(px+1,px+cnt1+1);
	//for(int i=1;i<=cnt1;i++) cout<<px[i]<<" ";cout<<endl;
	for(int i=1;i<cnt1;i++){
		if(sig(px[i+1]-px[i]))
		ans+=(px[i+1]-px[i])*(scan((px[i+1]+px[i])/2));
	}
	printf("%0.2lf",ans-eps);//玄学优化常数
	return 0;
}

例题 3 Last Stardust

n个点，一条固定线段AB，求多少点对满足一个点在另一个点与AB形成的三角形内，数据保证不会有三点共线。

对于两个点，只要满足与AB两点的极角，一大一小即满足题意。转化为二位偏序问题。

按照与AB的极角排序后，树状数组依次枚举统计答案即可。

（注意AB两侧的点分开计算）

（另外关于按照AB极角排序，可以按照与叉积排序后搞定顺序，或者用余弦定理搞定cos，再lowbound搞定顺序，精度上优选叉积排序，但是余弦定理相对好写）

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int getint(){
	int summ=0,f=1;char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-')f=-1,ch=getchar();
	for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
	return summ*f;
}
#define pii pair<int,int>
const int M=1e5+5;
const double pi=acos(-1.0);
const double eps=1e-9;

struct point{
	int x,y;
	point(int xx=0,int yy=0){
		x=xx;y=yy;
	}
	point operator - (point r) {
		return point(r.x-x,r.y-y);
	}
	int operator ^ (point r) {
		return -y*r.x+
		x*r.y;
	}
	int operator * (point r) {
		return x*r.x+y*r.y;
	}
};

double dis(point aa,point bb){
	return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}

int tr[2*M],res,n,m;
point arr[M],AA,BB;
double angel[M][2],pos[2*M];
pii id[M];
inline void add(int x,int val){
	for(int i=x;i<=2*M;i+=(i&-i)) tr[i]+=val;
}
inline int qu(int x){
	int ans=0;
	for(int i=x;i>0;i-=(i&-i)) ans+=tr[i];
	return ans;
}
double getangel(double a,double b,double c){
	return acos((b*b+c*c-a*a)/(2*c*b));
}
int solve(point A,point B){
	memset(tr,0,sizeof(tr));
	m=0;int cnt=0,ans=0;
	for(int i=1;i<=n;i++){
		if( ((A-B) ^ (A-arr[i])) > 0){
			m++;point P=arr[i];
			double disPA=dis(P,A),disPB=dis(P,B),disAB=dis(A,B);
			angel[m][0]=getangel(disPB,disPA,disAB);
			angel[m][1]=pi-getangel(disPA,disPB,disAB);
			pos[++cnt]=angel[m][0],pos[++cnt]=angel[m][1];
		}
	}
	sort(pos+1,pos+cnt+1);
	for(int i=1;i<=m;i++){
		id[i].first=lower_bound(pos+1,pos+cnt+1,angel[i][0]) - pos;
		id[i].second=lower_bound(pos+1,pos+cnt+1,angel[i][1]) - pos;
	}
	sort(id+1,id+m+1);
	for(int i=1;i<=m;i++){
		ans+=qu(2*M)-qu(id[i].second);
		add(id[i].second,1);
	}return ans;
}
signed main(){
	cin>>n>>AA.x>>AA.y>>BB.x>>BB.y;
	for(int i=1;i<=n;i++) arr[i].x=getint(),arr[i].y=getint();
	res=solve(AA,BB)+solve(BB,AA);
	cout<<res;
	return 0;
}

例题4 [JSOI2016]炸弹攻击2

注意到所有敌人都在塔和能量源的上方，所以一个合法光线等价于一个三元组(l,mid,r)(l,mid,r)满足(s−>l)<(s−>mid)<(s−>r)(s->l)<(s->mid)<(s->r)且(s−>l)(s->l)与(s−>r)(s->r)夹角小于180180。

于是我们按照级角排序，维护每一个线段作为左端点的最右端点（双指针维护），然后提前维护一些前缀和，可以做到对每个左端点O(1)O(1)计算答案即可。

关于实现：在级角排序时，最方便用atan2atan2，如果要叉积比较必须要选一组基准边，保证一定可以构成排序，不要像我一样sb到直接比较两边叉积。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=10000;
struct point{
	int x,y;
	point(int _x=0.0,int _y=0.0){
		x=_x;y=_y;
	}
	point operator + (point b){
		return point(x+b.x,y+b.y);
	}
	point operator - (point b){
		return point(b.x-x,b.y-y);
	}
	point operator * (int k){
		return point(x*k,y*k);
	}
	int operator ^ (point b){
		return x*b.y-y*b.x;
	}
}d[M],s[M],t[M];
struct node{
	point vec;int ty;double angle;	
}v[M];
inline bool cmp(node a,node b){
	return a.angle<b.angle;
}
int st[M],sum[M],sd[M],n,m,D,T,S;
inline int Solve(point p){
	int cnt=0;
	for(int i=1;i<=D;i++) v[++cnt].vec=p-d[i],v[cnt].ty=0,v[cnt].angle=atan2(v[cnt].vec.y,v[cnt].vec.x);
	for(int i=1;i<=T;i++) v[++cnt].vec=p-t[i],v[cnt].ty=1,v[cnt].angle=atan2(v[cnt].vec.y,v[cnt].vec.x);
	sort(v+1,v+cnt+1,cmp);
	for(int i=1;i<=cnt;i++) v[i+cnt]=v[i];
	cnt=cnt*2;
	for(int i=1;i<=cnt;i++){
		st[i]=st[i-1];sum[i]=sum[i-1];sd[i]=sd[i-1];
		if(v[i].ty){
			sum[i]+=sd[i];
			st[i]++;
		}
		else sd[i]++;
	}
	int ans=0;
	for(int i=1,j=1;i<=cnt/2;i++){
		if(v[i].ty==0) continue;
		j=max(j,i);
		while(j+1<i+cnt/2&&(v[i].vec^v[j+1].vec)>0) j++;
		ans+=sum[j]-sum[i]-sd[i]*(st[j]-st[i]);
	}
	return ans;
}
signed main(){
	cin>>D;for(int i=1;i<=D;i++) cin>>d[i].x>>d[i].y;
	cin>>S;for(int i=1;i<=S;i++) cin>>s[i].x>>s[i].y;
	cin>>T;for(int i=1;i<=T;i++) cin>>t[i].x>>t[i].y;
	int ans=0;
	for(int i=1;i<=S;i++) ans+=Solve(s[i]);
	cout<<ans<<endl;
	return 0;
}

例题5 [SCOI2015]小凸想跑步

对每条边与AB等分面积中位线可以用叉积暴算后化简，发现是一条直线（这个从几何角度分析也可以发现）

于是就是个裸的半平面交了

（时刻关心除数为0的情况，ta真的很致命qwq

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
#define double long double
inline int getint(){
	int summ=0,f=1;char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-')f=-1,ch=getchar();
	for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
	return summ*f;
}
const int M=1e6+5,pi=acos(-1),eps=1e-9;
int n,cnt=0;
struct point{
	double x,y;
	point(double _x=0,double _y=0){x=_x,y=_y;}
	friend point operator - (point x,point y){return point(y.x-x.x,y.y-x.y);}
	friend point operator + (point x,point y){return point(y.x+x.x,y.y+x.y);}
	friend double operator ^ (point x,point y){return x.x*y.y-x.y*y.x;}
	friend point operator * (point x,double k){return point(x.x*k,x.y*k);}
}p[M],A,B,C,D;
inline int pp(point x,point y){return (int)x.x*(int)y.y-(int)x.y*(int)y.x;}
inline int sig(double x){
	if(fabs(x)<=eps) return 0;
	return (x>0)?1:-1;
}
struct line{
	point a,b;double angle;
	friend bool operator < (line p,line q){
		if(sig(p.angle-q.angle))  return p.angle<q.angle;
		return sig((p.a-q.a)^(p.a-q.b))>0;
	}
}l[M];
double a,b,c;
int que[M],h=1,t=0;
void print(point x){
	printf("%0.4lf %0.4lf\n",x.x,x.y); 
}
point Cross(line ll,line rr){
	double S1=(ll.a-ll.b)^(rr.a-rr.b),S2=(ll.a-rr.b)^(rr.a-ll.a);
	return ll.a+(ll.a-ll.b)*(S2/S1);
}
inline bool pd(point a,line ll){
	return sig((ll.a-ll.b)^(ll.a-a))<0;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	A=p[1];B=p[2];	
	
	p[n+1]=p[1];double Ans=0;
	for(int i=1;i<=n;i++){
		Ans=Ans+(p[i]^p[i+1]);
	}Ans=fabs(Ans);
	p[n+1]=p[1];
	for(int i=1;i<=n;i++) cnt++,l[cnt].a=p[i],l[cnt].b=p[i+1];
	
	for(int i=2;i<=n;i++){
		C=p[i],D=p[i+1];
		a=-D.y+C.y+B.y-A.y,b=A.x-B.x-C.x+D.x;
		c=B.x*A.y-A.x*B.y-D.x*C.y+C.x*D.y;
		point P,Q;
		if(!sig(a)){
			P.x=0;P.y=-c/b;
		}
		else{
			P.x=-c/a,P.y=0;
		}
		cnt++;l[cnt].a=P,l[cnt].b=P+point(b,-a);
	}
	
	for(int i=1;i<=cnt;i++){
		l[i].angle=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
	}
	sort(l+1,l+cnt+1);int tot=0;
	for(int i=1;i<=cnt;i++){
		if(i>1&&!sig(l[i].angle-l[tot].angle)){
			continue;
		}
		++tot;l[tot]=l[i];
	}
	cnt=tot;
	for(int i=1;i<=cnt;i++){
		while(h<t&&pd(Cross(l[que[t-1]],l[que[t]]),l[i])) t--;
		while(h<t&&pd(Cross(l[que[h]],l[que[h+1]]),l[i])) h++;
		que[++t]=i;
	}
	while(h<t-1&&pd(Cross(l[que[t-1]],l[que[t]]),l[que[h]])) t--;
	while(h<t-1&&pd(Cross(l[que[h]],l[que[h+1]]),l[que[t]])) h++;
	if(t-h<2){
		cout<<"0.0000";return 0;
	}
	que[t+1]=que[h];tot=0;
	for(int i=h;i<=t;i++){
		++tot;p[tot]=Cross(l[que[i]],l[que[i+1]]);
	}
	p[tot+1]=p[1];double ans=0;
	for(int i=1;i<=tot;i++){
		ans=ans+(p[i]^p[i+1]);
	}ans=fabs(ans);
	printf("%0.4Lf",ans/Ans);
	return 0;
}

例题6 [HNOI2012]射箭

不难发现对一个标靶合法射击二次函数的a,ba,b取值满足一次函数关系，故二分后半平面交即可，只要半平面有解即是可行。

（对于这种可能不是围成封闭图形的半平面交，预处理要加上四条边界线）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
#define double long double
const int M=2e5+5;
const double eps=1e-18,inf=1e16;
inline int sig(double x){
	if(fabs(x)<=eps) return 0;
	return (x>0)?1:-1;
}
struct point{
	double x,y;
	point(double xx=0.0,double yy=0.0){x=xx,y=yy;}
	friend point operator + (point x,point y){return point(x.x+y.x,x.y+y.y);}
	friend point operator - (point x,point y){return point(y.x-x.x,y.y-x.y);}
	friend double operator ^ (point x,point y){return x.x*y.y-x.y*y.x;}
	friend point operator * (point x,double k){return point(x.x*k,x.y*k);}
};
struct line{
	point a,b;double angle;int id;
	friend bool operator < (line l,line r){
		if(!sig(l.angle-r.angle)) return sig((l.a-r.a)^(l.a-r.b))>=0;
		return l.angle<r.angle;
	}
}l[M],ll[M];
struct Q{
	double x,y,yy;
}q[M];
int n,m,tot,cnt,sta[M],h=1,t=0;
bool pd(point a,line l){
	return sig((l.a-l.b)^(l.a-a))<0;
}
point Cross(line l,line r){
	double S=((l.a-l.b)^(r.a-r.b)),S1=((l.a-r.a)^(l.a-r.b));
	return l.a+(l.a-l.b)*(S1/S);
}
inline bool Check(int mid){
	for(int i=1;i<=tot;i++) l[i]=ll[i];
	cnt=0;
	for(int i=1;i<=tot;i++){
		if(l[i].id>mid) continue;
		if(cnt>=1&&sig(l[i].angle-l[cnt].angle)==0) continue;
		++cnt;l[cnt]=l[i];
	}
	h=1,t=0;
	for(int i=1;i<=cnt;i++){
		while(h<t&&pd(Cross(l[sta[t]],l[sta[t-1]]),l[i])) t--;
		while(h<t&&pd(Cross(l[sta[h]],l[sta[h+1]]),l[i])) h++;
		sta[++t]=i;
	}
	while(h<t-1&&pd(Cross(l[sta[t]],l[sta[t-1]]),l[sta[h]])) t--;
	while(h<t-1&&pd(Cross(l[sta[h]],l[sta[h+1]]),l[sta[t]])) h++;
	if(t-h+1<3) return false;
	return true;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%Lf%Lf%Lf",&q[i].x,&q[i].y,&q[i].yy);
		double a=q[i].x*q[i].x,b=q[i].x,c=-q[i].y;
		++tot;ll[tot].a=point(0.0,-c/b),ll[tot].b=point(-c/a,0.0);ll[tot].id=i;;
		
		a=q[i].x*q[i].x,b=q[i].x,c=-q[i].yy;
		++tot;ll[tot].b=point(0.0,-c/b),ll[tot].a=point(-c/a,0.0);ll[tot].id=i;;
	}
	ll[++tot]=(line){(point){-inf,eps},(point){-eps,eps},0,0};
	ll[++tot]=(line){(point){-eps,eps},(point){-eps,inf},0,0};
	ll[++tot]=(line){(point){-eps,inf},(point){-inf,inf},0,0};
	ll[++tot]=(line){(point){-inf,inf},(point){-inf,eps},0,0};
	for(int i=1;i<=tot;i++) ll[i].angle=atan2(ll[i].b.y-ll[i].a.y,ll[i].b.x-ll[i].a.x);
	sort(ll+1,ll+tot+1);
	int lll=1,rrr=n;
	while(lll<=rrr){
		if(rrr-lll<=1){
			if(Check(rrr)) cout<<rrr;
			else cout<<lll;
			break;
		}
		int mid=lll+rrr>>1;
		if(Check(mid)) lll=mid;
		else rrr=mid-1;
	}
	return 0;
}