洛谷P3222 [HNOI2012]射箭（计算几何，半平面交，双端队列）

设抛物线方程为\(y=ax^2+bx(a<0,b>0)\)，我们想要求出一组\(a,b\)使得它尽可能满足更多的要求。这个显然可以二分答案。

如何check当前的\(mid\)是否合法呢？每一个限制条件形如\(y_{i_1}\le ax_i^2+bx_i\le y_{i_2}\)，也就是\(\frac{y_{i_1}}{x_i}\le x_ia+b\le \frac{y_{i_2}}{x_i}\)。把\(a,b\)看成自变量，实际上每个不等式就是一个半平面，我们需要求出半平面交。

需要掌握向量、叉积等少量基础算法（不过做到这题的大佬们肯定会了），可以参考xzy巨佬的总结。

有一种\(O(n^2)\)的动态插入半平面的做法，可以通过原题数据（目前最优解第一版大部分是这种写法），也可以参考xzy巨佬的总结。

蒟蒻构造了一组边数很多的半平面交，可以卡掉这种写法，目前rank1的代码本机需要20s以上。

一些hack数据可以从这里下（部分转自liu_runda）

链接: https://pan.baidu.com/s/1Te0G-L2JrRu361qKAGorhQ

提取码: ea9m

谈一谈正经的\(O(n\log n)\)的实现吧。以下内容从蒟蒻的总结里㧟的。

我们用有向直线（一个点和一个方向向量）表示半平面，以下默认半平面在有向直线的左侧。

对有向直线按方向向量的极角排序，维护一个双端队列，存储当前构成半平面的直线以及相邻两直线的交点。

每次加入一条有向直线，如果队首/队尾的交点在直线右侧（用叉积判）则弹掉队首/队尾的直线。

为什么这样是对的呢？因为加入直线的单调性，所以要被弹出的直线一定在队首或队尾。感兴趣的话可以自己手画一些例子来理解。

需要注意的细节：

加入直线时，先弹队尾，再弹队首。
最后还要检查队尾交点是否在队首直线的右侧，如果是也要弹掉。
特判平行直线，在右侧的要弹掉。
如果题目给出的半平面不一定有限制边界，则应该手动加入一个INF边界。

算法的复杂度瓶颈在排序，因此预先将这些有向直线排好序，二分check时忽略编号大于mid的直线就可以了。时间复杂度\(O(n\log n)\)。

注意这题的坐标范围是\(1e9\)范围，因此INF设到\(1e10\)以上，EPS设到\(1e-10\)以下。

#include<bits/stdc++.h>

#define RG register

#define I inline

#define R RG int

#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))

using namespace std;

typedef double DB;

const int SZ=1<<19,N=2e5+9;

const DB INF=1e11,EPS=1e-11;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

inline int in(){

	G;while(*ip<'-')G;

	R x=*ip&15;G;

	while(*ip>'-'){x*=10;x+=*ip&15;G;}

	return x;

}

struct Vec{

	DB x,y;

	I Vec(){}

	I Vec(DB a,DB b){x=a;y=b;}

	I Vec operator+(Vec a){return Vec(x+a.x,y+a.y);}

	I Vec operator-(Vec a){return Vec(x-a.x,y-a.y);}

	I Vec operator*(DB a){return Vec(x*a,y*a);}//数乘

	I DB operator^(Vec a){return x*a.y-y*a.x;}//叉积

}k[N];

struct Line{

	Vec p,v;DB ang;int id;

	I Line(){}

	I Line(Vec a,Vec b,R c){p=a,v=b-a,ang=atan2(v.y,v.x),id=c;}

	I bool operator<(Line&a){return ang<a.ang;}

	I bool Right(Vec&a){return (v^(a-p))<-EPS;}

	I friend Vec Cross(Line&a,Line&b){//求直线交点

		return a.p+a.v*((b.v^(b.p-a.p))/(b.v^a.v));

	}

}a[N],q[N];

int p=0,l=1,r,mid;

bool HalfPlane(Line*a,Line*e){//求半平面是否有交

	R n=e-a,i=0,h=0,t=0;

	while(a[i].id>mid)++i;

	for(q[0]=a[i++];i<n;++i){

		if(a[i].id>mid)continue;

		while(h<t&&a[i].Right(k[t-1]))--t;

		while(h<t&&a[i].Right(k[h]))++h;

		if(a[i].ang!=q[t].ang)q[++t]=a[i];

		else if(a[i].Right(q[t].p))q[t]=a[i];

		if(h<t)k[t-1]=Cross(q[t-1],q[t]);

	}

	while(h<t&&q[h].Right(k[t-1]))--t;

	return t-h>1;

}

int main(){

	r=in();

	for(R i=1;i<=r;++i){

		DB x=in(),y1=in(),y2=in();

		a[++p]=Line(Vec(0,y1/x),Vec(1,y1/x-x),i);

		a[++p]=Line(Vec(1,y2/x-x),Vec(0,y2/x),i);

	}//边界要设EPS不能设0，因为a、b为0均不合题意

	a[++p]=Line(Vec(-INF,EPS),Vec(-EPS,EPS),0);

	a[++p]=Line(Vec(-EPS,EPS),Vec(-EPS,INF),0);

	a[++p]=Line(Vec(-EPS,INF),Vec(-INF,INF),0);

	a[++p]=Line(Vec(-INF,INF),Vec(-INF,EPS),0);

	sort(a+1,a+p+1);

	while(l<r){

		mid=(l+r+1)>>1;

		HalfPlane(a+1,a+p+1)?l=mid:r=mid-1;

	}

	cout<<l<<endl;

	return 0;

}

巴特西

洛谷P3222 [HNOI2012]射箭（计算几何，半平面交，双端队列）

最新文章

热门文章