一, 题面
POJ3470
二, 分析
POJ 感觉是真的老了.
这题需要一些预备知识: 扫描线, 离散化, 线段树. 线段树是解题的关键, 因为这里充分利用了线段树区间修改的高效性, 再加上一个单点查询.
为什么需要离散化?
坐标太分散了, 据说可以到 long long, 但是就这么多个点, 所以离散化一下, 方便处理.
为什么用扫描线算法?
用扫描线, 可以方便的求出一个 bird 到 wall 的距离, 因为是顺着一个方向扫的 (这题需要从四个方向扫), 所以保证了准确性和高效性.
为什么用线段树?
用线段树非常明显, 因为墙有这么多, 并且结合扫描线, 墙可能会有重叠部分, 而线段树的 lazy 标记用法刚好可以完美的使用.
然后就是一些思维方面的了, 因为 bird 可以朝 4 个方向飞, 所以需要从 4 个方向扫, 如果不从 4 个方向扫, 每次处理一个 bird 非常不好处理.
然后就是写代码的时候要细心, 可能有很多细节问题.
三, AC 代码
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <fstream>
- #include <cstring>
- #include <cmath>
- using namespace std;
- #define Lson(x) (x<<1) // 左儿子
- #define Rson(x) (x<<1|1) // 左儿子
- #define Mid(l, r) ( (l+r)>>1 )
- #define LL long long
- const int MAXN = 2e5 + 15;
- int N, M; //N is the number of wall
- int ans[MAXN];
- vector<LL> cor_x, cor_y;
- struct Wall
- {
- LL x1, y1;
- LL x2, y2;
- }W[MAXN];
- struct Bird
- {
- LL x, y;
- }B[MAXN];
- struct Dist
- {
- int id;
- LL dist;
- Dist()
- {
- // 这里必须用 long long 的无穷大, 因为给的数据会超过 int
- // 找这个 WA 点找了很久
- dist = __LONG_LONG_MAX__;
- }
- }D[MAXN];
- enum Type
- {
- WALL, BIRD
- };
- struct Object // 处理对象
- {
- Type type;
- int id; //bird's or wall's id
- int x, y1, y2;
- 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 &t)const
- {
- return x < t.x;
- }
- };
- struct SegTree
- {
- //Value 的值表示线段树维护区间的墙的 id
- int Left[MAXN<<2], Right[MAXN<<2], Value[MAXN<<2];
- // 线段树初始化
- void init(int p, int l, int r)
- {
- Left[p] = l;
- Right[p] = r;
- Value[p] = 0;
- if(l == r)
- return;
- init(Lson(p), l, Mid(l, r));
- init(Rson(p), Mid(l, r) + 1, r);
- }
- // 出现了墙, 则维护区间
- void update(int p, int l, int r, int id)
- {
- if(Left[p] == l && Right[p] == r)
- {
- Value[p] = id;
- return;
- }
- if(Value[p]> 0)
- {
- Value[Lson(p)] = Value[p];
- Value[Rson(p)] = Value[p];
- Value[p] = 0; // 一定记得清 0
- }
- // int mid = Mid(l, r);
- int mid = Mid(Left[p], Right[p]);
- if(l> mid)
- {
- update(Rson(p), l, r, id);
- }
- else if(r <= mid)
- {
- update(Lson(p), l, r, id);
- }
- else
- {
- update(Lson(p), l, mid, id);
- update(Rson(p), mid + 1, r, id);
- }
- }
- // 出现了 bird, 在线段树中寻找合适的 wall 被撞
- // loc 如果是沿 x 轴飞, 那么 loc 应该是 y 值, 只有这样才能保证撞的有效
- int find(int p, int loc)
- {
- if(Left[p] == Right[p] && Left[p] == loc)
- return Value[p];
- if(Value[p]> 0)
- {
- Value[Lson(p)] = Value[p];
- Value[Rson(p)] = Value[p];
- Value[p] = 0; // 一定记得清 0
- }
- int mid = Mid(Left[p], Right[p]);
- if(loc> mid)
- {
- return find(Rson(p), loc);
- }
- else
- {
- return find(Lson(p), loc);
- }
- }
- }STree;
- // 计算距离
- LL cal_dis(bool dir, int x1, int x2)
- {
- LL d1, d2;
- if(dir)
- {
- d1 = cor_x[x1 - 1];
- d2 = cor_x[x2 - 1];
- }
- else
- {
- d1 = cor_y[x1 - 1];
- d2 = cor_y[x2 - 1];
- }
- d1 = d1 - d2;
- if(d1 <0)
- return -d1;
- else
- return d1;
- }
- void scan(const vector<Object> &arr, bool dir) //dir 表示方向
- {
- STree.init(1, 1, max(cor_x.size(), cor_y.size()) + 15);
- vector<Object>::const_iterator itr;
- for(itr = arr.begin(); itr != arr.end(); itr++)
- {
- if(itr->type == WALL)
- {
- STree.update(1, itr->y1, itr->y2, itr->id);
- }
- else
- {
- int pos = STree.find(1, itr->y1);
- if(pos)
- {// 一定要保证墙存在!
- LL len;
- if(dir) // dir = 1 表示沿 x 轴方向
- //len = cal_dis(dir, itr->x, W[pos].x1);
- len = min( cal_dis(true, W[pos].x1, itr->x), cal_dis(true, W[pos].x2, itr->x) );
- else
- //len = cal_dis(dir, itr->x, W[pos].y1);
- len = min( cal_dis(false, W[pos].y1, itr->x), cal_dis(false, W[pos].y2, itr->x) );
- if(len <D[itr->id].dist)
- {
- D[itr->id].dist = len;
- D[itr->id].id = pos;
- }
- }
- }
- }
- }
- void fly_x() // 假设现在 bird 都是沿着 x 轴方向飞行
- {
- vector<Object> T; // 存储扫描时要处理的对象
- for(int i = 1; i <= N; i++)
- {
- T.push_back(Object(W[i].x1, W[i].y1, W[i].y2, i, WALL) );
- if(W[i].x1 != W[i].x2) // 必须要加末端, 因为 bird 可能在延长线上
- {
- T.push_back(Object(W[i].x2, W[i].y1, W[i].y2, i, WALL) );
- }
- }
- for(int i = 1; i <= M; i++)
- {
- T.push_back(Object(B[i].x, B[i].y, 0, i, BIRD) );
- }
- sort(T.begin(), T.end());
- scan(T, true);
- reverse(T.begin(), T.end());
- scan(T, true);
- }
- void fly_y() // 假设现在 bird 都是沿着 y 轴方向飞行
- {
- vector<Object> T; // 存储扫描时要处理的对象
- for(int i = 1; i <= N; i++)
- {
- T.push_back(Object(W[i].y1, W[i].x1, W[i].x2, i, WALL) );
- if(W[i].y1 != W[i].y2)
- {
- T.push_back(Object(W[i].y2, W[i].x1, W[i].x2, i, WALL) );
- }
- }
- for(int i = 1; i <= M; i++)
- {
- T.push_back(Object(B[i].y, B[i].x, 0, i, BIRD) ); // 注意顺序
- }
- sort(T.begin(), T.end());
- scan(T, false);
- reverse(T.begin(), T.end());
- scan(T, false);
- }
- void discretization() // 离散化处理
- {
- sort(cor_x.begin(), cor_x.end());
- sort(cor_y.begin(), cor_y.end());
- cor_x.erase(unique(cor_x.begin(), cor_x.end() ), cor_x.end() );
- cor_y.erase(unique(cor_y.begin(), cor_y.end() ), cor_y.end() );
- for(int i = 1; i <= N; i++)
- {
- W[i].x1 = lower_bound(cor_x.begin(), cor_x.end(), W[i].x1) - cor_x.begin() + 1;
- W[i].x2 = lower_bound(cor_x.begin(), cor_x.end(), W[i].x2) - cor_x.begin() + 1;
- W[i].y1 = lower_bound(cor_y.begin(), cor_y.end(), W[i].y1) - cor_y.begin() + 1;
- W[i].y2 = lower_bound(cor_y.begin(), cor_y.end(), W[i].y2) - cor_y.begin() + 1;
- }
- for(int i = 1; i <= M; i++)
- {
- B[i].x = lower_bound(cor_x.begin(), cor_x.end(), B[i].x) - cor_x.begin() + 1;
- B[i].y = lower_bound(cor_y.begin(), cor_y.end(), B[i].y) - cor_y.begin() + 1;
- }
- }
- int main()
- {
- //freopen("input.txt", "r", stdin);
- scanf("%d %d", &N, &M);
- for(int i = 1; i <= N; i++)
- {
- scanf("%I64d %I64d %I64d %I64d", &W[i].x1, &W[i].y1, &W[i].x2, &W[i].y2);
- if(W[i].x1> W[i].x2) swap(W[i].x1, W[i].x2);
- if(W[i].y1> W[i].y2) swap(W[i].y1, W[i].y2);
- cor_x.push_back(W[i].x1);
- cor_x.push_back(W[i].x2);
- cor_y.push_back(W[i].y1);
- cor_y.push_back(W[i].y2);
- }
- for(int j = 1; j <= M; j++)
- {
- scanf("%I64d %I64d", &B[j].x, &B[j].y);
- cor_x.push_back(B[j].x);
- cor_y.push_back(B[j].y);
- }
- discretization();
- fly_x();
- fly_y();
- memset(ans, 0, sizeof(ans));
- for(int i = 1; i <= M; i++)
- {
- ans[ D[i].id ]++;
- }
- for(int i = 1; i <= N; i++)
- {
- printf("%d\n", ans[i]);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3012440.html