A40795. 轨道炮
填空题
困难
知识点
题目描述
轨道炮
题目描述
小明在玩一款战争游戏。地图上一共有 N 个敌方单位，可以看作 2D 平面上的点。其中第 i 个单位在 0 时刻的位置是 (Xi, Yi)，方向是 Di (上下左右之一, 用’U’/’D’/’L’/’R’ 表示)，速度是 Vi。小明的武器是轨道炮，只能使用一次，不过杀伤力巨大。小明可以选择在某个非负整数时刻释放轨道炮，轨道炮一次可以消灭在一条直线 (平行于坐标轴) 上的所有敌方单位。请你计算小明最多能消灭多少敌方单位。
输入
输入第一行包含一个整数 N。
以下 N 行每行包含 3 个整数 Xi, Yi, Vi，以及一个大写字符 Di。
输出
输出一个整数代表答案。
样例输入
4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L
样例输出
3
参考答案
#include
using namespace std;
int X[1010],Y[1010],vx[1010],vy[1010];
int mx=0;
int n;
void f(int X[],int vx[])
{
for(int i=1;i<n;i++)
{
unordered_map
int cnt=1;
for(int j=i+1;j<=n;j++)
{
if(vx[i]==vx[j])
{
if(X[i]==X[j])
cnt++;
mx=max(cnt,mx);
continue;
}
int dx=X[i]-X[j],dv=vx[j]-vx[i];
int t=dx/dv;
if(dx%dv||t<0) continue;
m[t]++;
mx=max(mx,m[t]+cnt);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int v;
char d;
cin>>X[i]>>Y[i]>>v>>d;
if(d=='R')
vx[i]=v;
if(d=='L')
vx[i]=-v;
if(d=='U')
vy[i]=v;
if(d=='D')
vy[i]=-v;
}
f(X,vx);
f(Y,vy);
cout<<mx;
return 0;
}
上一题
下一题