码农场
傻鸟：在二维平面上有N堵水平或垂直的墙，放M只傻鸟，每只傻鸟会撞死在最近的那堵墙上。求最后每堵墙上有多少团血肉模糊的尸体！
3.3活用各种数据结构
线段树和平方分割
中国人出的题目就是这么和谐，不过难度还是有的。思路类似于黑白棋 POJ 3109 Inner Vertices 的扫描线算法，一层一层地染色。首先只考虑傻鸟垂直飞的情况，从Y坐标大的地方往下扫描（此时小鸟相当于往上飞，相对运动嘛）。用一个线段树表示当前区间属于哪堵墙的地盘，每堵墙的x1，x2坐标作为l和r，区间的值为自己的id。扫描线往下移动的过程中就是一个用id染色的过程，如果碰到鸟了，那么鸟的x坐标送到线段树里查到的id就是它要撞死的墙。
同理，水平飞行的时候只要将坐标反过来就行了。需要注意的是，出题人非常不严谨，没有告知坐标的最大范围，事实上这个值比0x3f3f3f3f大，害得我WA了一大天！
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define LEFT(x) (x << 1)
#define RIGHT(x) ((x << 1) | 1)
#define MID(x, y) ((x + y) >> 1)
#define MAXN 200010
enum Type
{
WALL, BIRD
};
struct Distance
{
int id, d; // 距离最近的墙的id以及距离
Distance()
{
d = INT_MAX; // 0x3f3f3f3f让我WA了无数次(┳＿┳)...
}
};
Distance the_distance[MAXN];
struct Wall
{
int x1, y1, x2, y2;
}wall[MAXN];
struct Bird
{
int x, y;
}bird[MAXN];
struct Object
{
int x;
int y1, y2;
int id;
Type type;
Object(int x, int y1, int y2, int id, Type type) : x(x), y1(y1), y2(y2), id(id), type(type) {};
bool operator < (const Object& other) const
{
return x < other.x;
}
};
vector <int> listx;
vector <int> listy;
int result[MAXN];
int N, M;
struct SegmentTree
{
int left[MAXN * 8], right[MAXN * 8], value[MAXN * 8];
void build(int p, int l, int r)
{
left[p] = l;
right[p] = r;
value[p] = 0;
if (l < r)
{
int mid = MID(l, r);
build(LEFT(p), l, mid);
build(RIGHT(p), mid + 1, r);
}
}
void set(int p, int l, int r, int v)
{
if (left[p] == l && right[p] == r)
{
value[p] = v;
return;
}
if (value[p] > 0)
{
value[LEFT(p)] = value[p];
value[RIGHT(p)] = value[p];
value[p] = 0;
}
int mid = MID(left[p], right[p]);
if (l > mid)
{
set(RIGHT(p), l, r, v);
}
else if (r <= mid)
{
set(LEFT(p), l, r, v);
}
else
{
set(LEFT(p), l, mid, v);
set(RIGHT(p), mid + 1, r, v);
}
}
int get(int p, int l)
{
if (left[p] == right[p] && left[p] == l)
{
return value[p];
}
if (value[p] > 0)
{
value[LEFT(p)] = value[p];
value[RIGHT(p)] = value[p];
value[p] = 0;
}
if (l > MID(left[p], right[p]))
{
return get(RIGHT(p), l);
}
else
{
return get(LEFT(p), l);
}
}
}tree;
int get_distance(bool vertical, int x, int y)
{
if (!vertical)
{
x = listx[x - 1];
y = listx[y - 1];
}
else
{
x = listy[x - 1];
y = listy[y - 1];
}
return abs(x - y);
}
void go(const vector<Object>& obj_array, bool vertical)
{
tree.build(1, 1, max(listx.size(), listy.size()) + 10);
for (vector<Object>::const_iterator it = obj_array.begin(); it != obj_array.end(); ++it)
{
if (it->type == WALL)
{
tree.set(1, it->y1, it->y2, it->id);
}
else
{
int p = tree.get(1, it->y1);
if (p)
{
int d = vertical ? min(get_distance(1, wall[p].y1, it->x), get_distance(1, wall[p].y2, it->x)) : min(get_distance(0, wall[p].x1, it->x), get_distance(0, wall[p].x2, it->x));
if (d < the_distance[it->id].d)
{
the_distance[it->id].d = d;
the_distance[it->id].id = p;
}
}
}
}
}
void fly_x()
{
vector<Object> obj_array;
for (int i = 1; i <= N; ++i)
{
obj_array.push_back(Object(wall[i].x1, wall[i].y1, wall[i].y2, i, WALL));
if (wall[i].x1 != wall[i].x2)
{
obj_array.push_back(Object(wall[i].x2, wall[i].y1, wall[i].y2, i, WALL));
}
}
for (int i = 1; i <= M; ++i)
{
obj_array.push_back(Object(bird[i].x, bird[i].y, 0, i, BIRD));
}
sort(obj_array.begin(), obj_array.end());
go(obj_array, false);
reverse(obj_array.begin(), obj_array.end());
go(obj_array, false);
}
void fly_y()
{
vector<Object> obj_array;
for (int i = 1; i <= N; ++i)
{
obj_array.push_back(Object(wall[i].y1, wall[i].x1, wall[i].x2, i, WALL));
if (wall[i].y1 != wall[i].y2)
{
obj_array.push_back(Object(wall[i].y2, wall[i].x1, wall[i].x2, i, WALL));
}
}
for (int i = 1; i <= M; ++i)
{
obj_array.push_back(Object(bird[i].y, bird[i].x, 0, i, BIRD));
}
sort(obj_array.begin(), obj_array.end());
go(obj_array, true);
reverse(obj_array.begin(), obj_array.end());
go(obj_array, true);
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i)
{
scanf("%d%d%d%d", &wall[i].x1, &wall[i].y1, &wall[i].x2, &wall[i].y2);
if (wall[i].x1 > wall[i].x2)
{
swap(wall[i].x1, wall[i].x2);
}
if (wall[i].y1 > wall[i].y2)
{
swap(wall[i].y1, wall[i].y2);
}
listx.push_back(wall[i].x1);
listx.push_back(wall[i].x2);
listy.push_back(wall[i].y1);
listy.push_back(wall[i].y2);
}
for (int i = 1; i <= M; ++i)
{
scanf("%d%d", &bird[i].x, &bird[i].y);
listx.push_back(bird[i].x);
listy.push_back(bird[i].y);
}
sort(listx.begin(), listx.end());
listx.erase(unique(listx.begin(), listx.end()), listx.end());
sort(listy.begin(), listy.end());
listy.erase(unique(listy.begin(), listy.end()), listy.end());
for (int i = 1; i <= N; ++i)
{
wall[i].x1 = lower_bound(listx.begin(), listx.end(), wall[i].x1) - listx.begin() + 1;
wall[i].x2 = lower_bound(listx.begin(), listx.end(), wall[i].x2) - listx.begin() + 1;
wall[i].y1 = lower_bound(listy.begin(), listy.end(), wall[i].y1) - listy.begin() + 1;
wall[i].y2 = lower_bound(listy.begin(), listy.end(), wall[i].y2) - listy.begin() + 1;
}
for (int i = 1; i <= M; ++i)
{
bird[i].x = lower_bound(listx.begin(), listx.end(), bird[i].x) - listx.begin() + 1;
bird[i].y = lower_bound(listy.begin(), listy.end(), bird[i].y) - listy.begin() + 1;
}
fly_x();
fly_y();
for (int i = 1; i <= M; ++i)
{
++result[the_distance[i].id];
}
for (int i = 1; i <= N; ++i)
{
printf("%d\n", result[i]);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return 0;
}
///////////////////////////End Sub//////////////////////////////////
| 13232546 | hankcs | 3470 | Accepted | 12768K | 3094MS | C++ | 5763B | 2014-08-02 20:05:06 |
