【题解】
意思是说每个靶子离射击点的距离为z.然后描述矩形靶子的左下角和右下角。
射击m次。每次射击靶子之后。靶子会毁坏(假如同一个点有多个靶子重叠，最前面那个靶子坏掉。其他靶子还可以射击)；
做法:
给每个子弹记录三个信息x,y,bianhao。即坐标以及各个子弹出现的先后顺序。
然后以靶子离射击点的距离为关键字从小到大排序。
处理第一个靶子是被哪一个子弹射击了。即在靶子所在范围内的子弹。且要求子弹的编号(射击顺序)最小。
这个问题可以用kd-tree来解决。
以子弹的点为元素建立kdtree
知道一个靶子是被哪个子弹射击之后。在kdtree中删掉这个子弹。然后继续处理下一个靶子。
编程复杂度很高。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 105000;
const int INF = 2100000000;
struct target
{
int mi_n[2], ma_x[2], z, n;
};
struct point
{
int min, n, dot, d[2],fa,l,r;
};
int n, m, root, now, txl, txr, tyl, tyr, ans[MAXN] = { 0 };
target rec[MAXN];
point t[MAXN];
void input_data()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d%d%d", &rec[i].mi_n[0], &rec[i].ma_x[0], &rec[i].mi_n[1], &rec[i].ma_x[1], &rec[i].z);
rec[i].n = i;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &t[i].d[0], &t[i].d[1]);
t[i].n = i;
}
}
bool cmp_1(point a, point b)
{
return a.d[now] < b.d[now];
}
void gengxin(int father, int son)
{
if (t[father].min > t[son].min)
{
t[father].min = t[son].min;
t[father].dot = t[son].dot;
}
}
void up_data(int rt)
{
t[rt].min = t[rt].n; t[rt].dot = rt; //dot可以说是当前这个子树的编号最小的点的节点。
if (t[rt].n == 0) //如果点已经删掉了
{
t[rt].min = INF;
t[rt].dot = 0;
}
int l = t[rt].l, r = t[rt].r;
if (l)
gengxin(rt, l);
if (r)
gengxin(rt, r);
}
int build(int begin, int end, int fa,int fx)
{
int m = (begin + end) >> 1;
now = fx;
nth_element(t + begin, t + m, t + end + 1, cmp_1);
t[m].fa = fa;
if (begin < m)
t[m].l = build(begin, m - 1, m, 1 - fx);
if (m < end)
t[m].r = build(m + 1, end, m, 1 - fx);
up_data(m);
return m;
}
bool inrange(int x, target b,int fx)
{
return ((b.mi_n[fx] <= x) && (x <= b.ma_x[fx]));
}
int query(int rt, int fx, int r, int xl, int xr, int yl, int yr)
{//r是当前处理的靶子编号 txl,txr,tyl,tyr是靶子信息。
//xl,xr,yl,yr是当前kd-tree的节点所在子树的所有点的范围(如果不确定就写成无穷大)
if (!rt)//我们会不断缩小这个范围。
return 0;
if (!t[rt].dot)
return 0;
if (txl <= xl && xr <= txr && tyl <= yl && yr <= tyr)
return t[rt].dot;
int t1 = 0,t2 = 0;
if (inrange(t[rt].d[fx], rec[r], fx))//这个节点的fx坐标在靶子范围内
{ //则左右儿子都要递归求解。则后序还要查看当前这个节点是否能更新。
if (fx == 0) //如果是以x轴排序
{
t1 = query(t[rt].l, 1-fx, r, xl, t[rt].d[0], yl, yr);
t2 = query(t[rt].r, 1-fx, r, t[rt].d[0], xr, yl, yr);
}
else//以y轴排序
{
t1 = query(t[rt].l, 1-fx, r, xl, xr, yl, t[rt].d[1]);
t2 = query(t[rt].r, 1-fx, r, xl, xr, t[rt].d[1], yr);
}
}
else//这个靶子的xy坐标没有完全把这个点包住
{//则只要返回左或右儿子
if (t[rt].d[fx] < rec[r].mi_n[fx])//大于这个节点的fx坐标 等号的情况上面已经考虑了
{
if (fx == 0)
return query(t[rt].r, 1-fx, r, t[rt].d[0], xr, yl, yr);
else
return query(t[rt].r, 1-fx, r, xl, xr, t[rt].d[1], yr);
}
if (rec[r].ma_x[fx] < t[rt].d[fx])//小于这个节点的fx坐标
{
if (fx == 0)
return query(t[rt].l, 1-fx, r, xl, t[rt].d[0], yl, yr);
else
return query(t[rt].l, 1-fx, r, xl, xr, yl, t[rt].d[1]);
}
}
int fi = 0; int temp = INF;
if (t1!=0)
if (t[t1].n < temp)//千万不要写成t[t1].min < temp
{//因为可能t[t1].min对应的点不在我们所需的范围内
//这个rt就已经返回的是所需的节点的编号了,不要乱来
temp = t[t1].n;
fi = t1;
}
if (t2 != 0)
if (t[t2].n < temp)
{
temp = t[t2].n;
fi = t2;
}
if (t[rt].n != 0 && t[rt].n < temp)//这是尝试用当前这个节点来更新。
if (inrange(t[rt].d[0],rec[r],0) && inrange(t[rt].d[1],rec[r],1))
{
temp = t[rt].n;
fi = rt;
}
return fi;
}
void adjust(int rt) //删掉一个点后调整相关点的信息
{
up_data(rt);
if (rt != root)
adjust(t[rt].fa);
}
bool cmp_2(target a, target b)
{
return a.z < b.z;
}
void get_ans()
{
root = build(1, m, 0, 0);
sort(rec + 1, rec + 1 + n, cmp_2);
for (int i = 1; i <= n; i++)
{
txl = rec[i].mi_n[0], txr = rec[i].ma_x[0], tyl = rec[i].mi_n[1], tyr = rec[i].ma_x[1];
int hit = query(root, 0, i, 0, INF, 0, INF);
if (hit != 0)
{
ans[t[hit].n] = rec[i].n;
t[hit].n = 0;
adjust(hit);
}
}
}
void output_ans()
{
for (int i = 1; i <= m; i++)
printf("%d
", ans[i]);
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
input_data();
get_ans();
output_ans();
return 0;
}