题解 | CattleBruisers-牛客假日团队赛9F题
F-Cattle Bruisers_牛客假日团队赛9
https://ac.nowcoder.com/acm/contest/1071/F
题目描述
Canmuu is out for revenge after being utterly defeated by Bessie in paintball and has challenged Bessie to a video game.In this game, Bessie starts out at point (BX, BY) in the coordinate grid
Unfortunately, Canmuu has sent
Each cattle bruiser carries a 'proximity' weapon to fire at Bessie; the weapon can hurt Bessie when the cattle bruiser is no further than
Bessie has a shield to protect herself from these attacks. However, she does not want to waste any of her shield's power, so she would like to know the maximum number of cattle bruisers within firing range for any (potentially non-integer) time t >= 0.
In order to avoid precision errors with real numbers, it is guaranteed that the answer produced will be the same whether the attack range is decreased to R-0.0001 or increased to R+0.0001.
输入描述:
* Line 1: Six space-separated integers: N, R, BX, BY, BVX, and BVY
* Lines 2..N+1: Line i+1 contains four space-separated integers: Xi, Yi, VXi, and VYi
输出描述:
* Line 1: Print a single integer denoting the maximum number of cattle bruisers within attack range at any point in time.
示例1
输入
3 1 0 0 0 2
0 -3 0 4
1 2 -1 1
1 -2 2 -1
输出
2
说明
Bessie starts at point (0, 0) and is moving at 2 units per second in the (positive) y-direction. There are 3 cattle bruisers, the first of which starts at point (0, -3) and travels 4 units per second in the y-direction. The maximum distance for a cattle bruiser to be in range of Bessie is 1 unit.
At time 1.5, Bessie is at point (0, 3), and the three bruisers are at points (0, 3), (-0.5, 3.5), and (4, -3.5). The first two cattle bruisers are within 1 unit of Bessie, while the third will never be within 1 unit of Bessie, so 2 is the most achievable.
解答
观察到题目中
和杀手都在动，所以考虑相对运动，以的位置作为原点，不动，只考虑杀手运动。让不动，直接杀手的位置和速度减去的即可。
考虑杀手攻击半径为
，转化一下即进入以)
为圆心，为半径的圆，就可攻击到。
所以我们只要求出每个杀手进入该圆与离开该圆的时间点即可。最后就可以对所以时间点进行排序，然后对整条时间线进行类似于扫描线的方法统计答案。
显然就是这样一张图：
求出直线与圆的交点即可.
设杀手起点为)
，速度为)
，设在tt时刻恰好在交点，那么：
化简得到一个一元二次方程：
解出来即可。(即程序里的
)
注意判断
均为0的情况。
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
using namespace std;
int n,r,top;
double bx,by,bvx,bvy,eps=1e-8,L,R;
struct node{
double x,y,vx,vy;
}a[500005];
struct TM{
double t;
int s;
}b[500005];
inline int read(){
int ret=0,ff=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
return ret*ff;
}
inline void work(double A,double B,double C){//a*t*t+b*t+c=0
if(fabs(A)<eps){
if(C<=0) L=0,R=1e9;
else L=R=-1;
return;
}
double delta=B*B-4*A*C;
if(delta<0){//一元二次方程判根
L=R=-1;
return;
}
L=(-B-sqrt(delta))/(2*A);
R=(-B+sqrt(delta))/(2*A);
if(L<0) L=0;
if(R<0) R=-1;
}
inline bool cmp(TM a,TM b){
return a.t<b.t;
}
signed main(){
n=read(),r=read();
bx=read(),by=read(),bvx=read(),bvy=read();
for(int i=1;i<=n;i++){
a[i].x=read()-bx;
a[i].y=read()-by;
a[i].vx=read()-bvx;
a[i].vy=read()-bvy;
}
for(int i=1;i<=n;i++){
double ds=a[i].x*a[i].x+a[i].y*a[i].y-r*r;
work(a[i].vx*a[i].vx+a[i].vy*a[i].vy,2*a[i].x*a[i].vx+2*a[i].y*a[i].vy,ds);
if(R!=-1) b[++top]=(TM){L,1},b[++top]=(TM){R,-1};
}
sort(b+1,b+top+1,cmp);
int sum=0,ans=0;
for(int i=1;i<=top;i++){
sum+=b[i].s;
ans=max(ans,sum);
}
printf("%lld",ans);
return 0;
} 来源： ιχγббб
投递哔哩哔哩等公司10个岗位
