本文主要是介绍bzoj2732: [HNOI2012]射箭【二分答案+半平面交】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
沫沫最近在玩一个二维的射箭游戏,如下图 1 所示,这个游戏中的 x 轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手,可以朝 0 至 90?中的任意角度(不包括 0度和 90度),以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力,并且光之箭没有箭身,箭的轨迹会是一条标准的抛物线,被轨迹穿过的所有靶子都认为被沫沫射中了,包括那些 只有端点被射中的靶子。这个游戏有多种模式,其中沫沫最喜欢的是闯关模式。在闯关模式中,第一关只有一个靶 子,射中这个靶子即可进入第二关,这时在第一关的基础上会出现另外一个靶子,若能够一箭 双雕射中这两个靶子便可进入第三关,这时会出现第三个靶子。依此类推,每过一关都会新出 现一个靶子,在第 K 关必须一箭射中前 K 关出现的所有 K 个靶子才能进入第 K+1 关,否则游戏 结束。沫沫花了很多时间在这个游戏上,却最多只能玩到第七关“七星连珠”,这让她非常困惑。 于是她设法获得了每一关出现的靶子的位置,想让你告诉她,最多能通过多少关
Input
输入文件第一行是一个正整数N,表示一共有N关。接下来有N行,第i+1行是用空格隔开的三个正整数xi,yi1,yi2(yi1
Output
仅包含一个整数,表示最多的通关数。
Sample Input
5
2 8 12
5 4 5
3 8 10
6 2 3
1 3 7
Sample Output
3
HINT
数据已加强By WWT15。特鸣谢!—2015.03.09
数据再加一组—2017.3.25
解题思路:
数据加强后WA了无数次终于过了,发现可以不用long double。
题目要求的是一个形如 y=ax2+bx(a<0,b>0) y = a x 2 + b x ( a < 0 , b > 0 ) 的二次函数,假如它要过靶 (x,y1,y2) ( x , y 1 , y 2 ) ,那么有: y1≤ax2+bx≤y2 y 1 ≤ a x 2 + b x ≤ y 2 ,化简后可得 −xa+y1x≤b≤−xa+y2x − x a + y 1 x ≤ b ≤ − x a + y 2 x ,现在一个靶就变成了两条关于 a,b a , b 的直线,要求的就是满足限制的最优的 a,b a , b 。
直接二分答案+半平面交判存在可行域即可。
要注意的地方有很多很多……
1.为了最后可行域是一个封闭空间,我们要先加四条边界线,还要体现 a<0,b>0 a < 0 , b > 0 的限制。
2.判断有解的条件是最后剩下至少三条直线,不然组不成一个封闭空间。
3.为了防止有 y1=y2 y 1 = y 2 导致两条直线重合gg的情况,要先把 y1−eps y 1 − e p s , y2+eps y 2 + e p s 。
4. eps e p s 要开 1e−10 1 e − 10 才行。
……
还有很多,代码不同,bug不同,自行寄刀片。
#include<bits/stdc++.h>
using namespace std;int getint()
{int i=0,f=1;char c;for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f;
}const int N=200005;
const double INF=1e10,eps=1e-10;
struct point
{double x,y;point(){}point(double _x,double _y):x(_x),y(_y){}inline friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}inline friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y);}inline friend double operator * (const point &a,const point &b){return a.x*b.y-a.y*b.x;}inline friend point operator * (const point &a,const double &b){return point(a.x*b,a.y*b);}
}p[N];
struct line
{point st,v;double ang;line(){}line(point _st,point _v):st(_st),v(_v){ang=atan2(v.y,v.x);}inline friend bool operator < (const line &a,const line &b){return a.ang<b.ang;}
}l[N];
int n,m;
double X[N],Y1[N],Y2[N];bool onleft(const point &a,const line &b)
{return b.v*(a-b.st)>0;
}point get_inter(line a,line b)
{double s1=(a.st-b.st)*b.v;double s2=b.v*(a.st+a.v-b.st);return a.st+a.v*(s1/(s1+s2));
}bool check(int mid)
{m=0;l[++m]=line(point(-INF,INF),point(0,-1));l[++m]=line(point(-INF,0),point(1,0));l[++m]=line(point(0,0),point(0,1));l[++m]=line(point(0,INF),point(-1,0));for(int i=1;i<=mid;i++){l[++m]=line(point(0,Y1[i]/X[i]),point(1,-X[i]));l[++m]=line(point(0,Y2[i]/X[i]),point(-1,X[i]));}sort(l+1,l+m+1);int head,tail=1;for(int i=2;i<=m;i++){if(l[i].ang!=l[tail].ang)l[++tail]=l[i];else if(onleft(l[i].st,l[tail]))l[tail]=l[i];}m=tail,head=tail=1;for(int i=2;i<=m;i++){while(head<tail&&!onleft(p[tail],l[i]))tail--;while(head<tail&&!onleft(p[head+1],l[i]))head++;l[++tail]=l[i];if(head<tail)p[tail]=get_inter(l[tail],l[tail-1]);}while(head<tail&&!onleft(p[tail],l[head]))tail--;return tail-head+1>=3;
}int main()
{//freopen("lx.in","r",stdin);//freopen("lx.out","w",stdout);n=getint();for(int i=1;i<=n;i++)X[i]=getint(),Y1[i]=getint()-eps,Y2[i]=getint()+eps;int L=1,R=n;while(L<=R){int mid=L+R>>1;check(mid)?L=mid+1:R=mid-1;}cout<<R;return 0;
}
这篇关于bzoj2732: [HNOI2012]射箭【二分答案+半平面交】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!