首页 > 代码库 > 扫描线
扫描线
1 HDU 5091 Beam Cannon
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define lc id << 1 20 #define rc id << 1 | 1 21 #define lson low, mid, lc 22 #define rson mid + 1, high, rc 23 24 struct Node { 25 int x, y1, y2, flag; 26 bool operator < (const Node& a) const { 27 if (x == a.x) { return flag > a.flag; } return x < a.x; 28 } 29 }; 30 31 typedef long long ll; 32 typedef pair<int, int> pii; 33 34 const int INF = 0x7fffffff; 35 const int maxn = 1e5 + 10; 36 int n, h, w, Size, x, y; 37 Node node[maxn]; 38 vector<int> v; 39 int Max[maxn * 4], lazy[maxn * 4]; 40 41 int get_id(int a) { return lower_bound(v.begin(), v.end(), a) - v.begin() + 1; } 42 void build(int low, int high, int id) { 43 Max[id] = lazy[id] = 0; if (low == high) { return; } 44 int mid = (low + high) / 2; build(lson); build(rson); 45 } 46 inline void push_up(int id) { Max[id] = max(Max[lc], Max[rc]); } 47 inline void push_down(int id) { 48 if (!lazy[id]) { return; } 49 lazy[lc] += lazy[id]; Max[lc] += lazy[id]; 50 lazy[rc] += lazy[id]; Max[rc] += lazy[id]; 51 lazy[id] = 0; 52 } 53 void update(int l, int r, int key, int low, int high, int id) { 54 if (l == low && r == high) { 55 lazy[id] += key; Max[id] += key; return; 56 } 57 int mid = (low + high) / 2; push_down(id); 58 if (r <= mid) { update(l, r, key, lson); } 59 else if (l >= mid + 1) { update(l, r, key, rson); } 60 else { update(l, mid, key, lson); update(mid + 1, r, key, rson); } 61 push_up(id); 62 } 63 64 int main() { 65 #ifdef __AiR_H 66 freopen("in.txt", "r", stdin); 67 // freopen("out.txt", "w", stdout); 68 #endif // __AiR_H 69 while (scanf("%d", &n) && n >= 0) { 70 // printf("n = %d\n", n); 71 scanf("%d %d", &w, &h); v.clear(); 72 for (int i = 0; i < n; ++i) { 73 scanf("%d %d", &x, &y); 74 node[i * 2] = Node{x, y - h, y, 1}; 75 node[i * 2 + 1] = Node{x + w, y - h, y, -1}; 76 v.push_back(y - h); v.push_back(y); 77 } 78 sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); 79 n *= 2; sort(node, node + n); Size = v.size(); build(1, Size, 1); 80 int id1, id2, ans = 0; 81 for (int i = 0; i < n; ++i) { 82 id1 = get_id(node[i].y1); id2 = get_id(node[i].y2); 83 update(id1, id2, node[i].flag, 1, Size, 1); 84 ans = max(ans, Max[1]); 85 } 86 printf("%d\n", ans); 87 } 88 #ifdef __AiR_H 89 printf("Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC); 90 #endif // __AiR_H 91 return 0; 92 }
扫描线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。