BZOJ1580 : [Usaco2009 Hol]Cattle Bruisers 杀手游戏
游戏 杀手
2023-09-11 14:15:04 时间
以贝茜为参照物,则贝茜固定于原点,每个杀手是一个圆心在某条射线上的圆。
解出每个杀手可以射杀贝茜的时间区间,然后扫描线即可,时间复杂度$O(n\log n)$。
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; int n,r,bx,by,bvx,bvy,x,y,vx,vy,i,m,t,ans;double L,R,inf=1e9; struct P{double x;int y;P(){}P(double _x,int _y){x=_x,y=_y;}}a[100010]; inline bool cmp(P a,P b){return a.x<b.x;} inline void getlr(ll a,ll b,ll c){ if(!a){ if(c<=0)L=0,R=inf;else L=R=-inf; return; } ll d=b*b-a*c*4; if(d<0){L=R=-inf;return;} L=(-1.0*b-sqrt(d))/2/a,R=(-1.0*b+sqrt(d))/2/a; if(R<0)L=R=-inf; if(L<0)L=0; } int main(){ scanf("%d%d%d%d%d%d",&n,&r,&bx,&by,&bvx,&bvy); while(n--){ scanf("%d%d%d%d",&x,&y,&vx,&vy); x-=bx,y-=by,vx-=bvx,vy-=bvy; getlr(vx*vx+vy*vy,2*(x*vx+y*vy),x*x+y*y-r*r); if(R>-1)a[++m]=P(L,1),a[++m]=P(R,-1); } sort(a+1,a+m+1,cmp); for(i=1;i<=m;i++)ans=max(ans,t+=a[i].y); return printf("%d",ans),0; }
相关文章
- HTML5游戏开发进阶指南
- 人工智能(AI)在游戏中的应用(下)
- 【BZOJ5303】[HAOI2018]反色游戏(Tarjan,线性基)
- 游戏服务器:到底使用UDP还是TCP
- 有奖征集活动系列——《iOS游戏编程之旅》已结束
- 直接操作游戏对象C#游戏开发
- 跳跃游戏 python
- 《Unity 游戏案例开发大全》一第6章 益智休闲类游戏——可乐可乐
- 《Android游戏开发详解》——第1章,第1.6节函数(在Java中称为“方法”更好)
- 《Unity 5.x游戏开发实战》一1.8 游戏测试与游戏选项卡
- macOS SwiftUI 游戏源码之艺术品记忆Memo游戏完整源码
- Python 制作软硬件交互游戏设备之太空探索者游戏(教程含源码)
- 《剑指offer》-- 栈的压入与弹出序列、把字符串转化为整数、扑克牌顺子、孩子们的游戏(圆圈中最后剩下的数)
- 微信小程序 | 游戏开发之接宝石箱子游戏
- Cocos2d-x 动手实现游戏主循环
- C++游戏研发-广州(年包40-60万)
- SD-WAN技术在海外游戏行业应用前景?