首页 > 代码库 > UVA1492 - Adding New Machine(扫描线)
UVA1492 - Adding New Machine(扫描线)
UVA1492 - Adding New Machine(扫描线)
题目链接
题目大意:给你N?M个格子,这些格子中某些格子是放了旧的机器,然后问现在要在这些格子放一台1?M的新机器,问有多少种放法。
解题思路:这题照样是可以转换成面积并来做,对于有旧机器(x,y)的格子,那么(x - M + 1,y)都是不可以放新机器的格子,还有从(H - M + 2,H)都是不可以放新机器的格子,所以覆盖的范围就要扩大。用扫描线算出这些不可以放新机器的格子,然后用总共的格子数剪掉就得到答案。分横着放和竖着放两种情况。注意M = 1的时候要特判,因为不存在横着和竖着两种情况。
代码:
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5e4 + 5;
typedef long long ll;
#define lson(x) (x<<1)
#define rson(x) ((x<<1) | 1)
int x[2][maxn], y[2][maxn];
struct Node {
int l, r, add, s;
void set (int l, int r, int add, int s) {
this->l = l;
this->r = r;
this->add = add;
this->s = s;
}
}node[8 * maxn];
struct Line {
int x, y1, y2, flag;
Line (int x, int y1, int y2, int flag) {
this->x = x;
this->y1 = y1;
this->y2 = y2;
this->flag = flag;
}
bool operator < (const Line& a) const {
return x < a.x;
}
};
vector<int> pos;
vector<Line> L;
int W, H, N, M;
void pushup (int u) {
if (node[u].add)
node[u].s = pos[node[u].r + 1] - pos[node[u].l];
else if (node[u].l == node[u].r)
node[u].s = 0;
else
node[u].s = node[lson(u)].s + node[rson(u)].s;
}
void build (int u, int l, int r) {
node[u].set (l, r, 0, 0);
if (l == r)
return;
int m = (l + r)>>1;
build (lson(u), l, m);
build (rson(u), m + 1, r);
pushup(u);
}
void update (int u, int l, int r, int v) {
if (node[u].l >= l && node[u].r <= r) {
node[u].add += v;
pushup(u);
return ;
}
int m = (node[u].l + node[u].r)>>1;
if (l <= m)
update (lson(u), l, r, v);
if (r > m)
update (rson(u), l, r, v);
pushup(u);
}
void init () {
for (int i = 0; i < N; i++)
scanf ("%d%d%d%d", &x[0][i], &y[0][i], &x[1][i], &y[1][i]);
}
ll solve (int w, int h, int x[2][maxn], int y[2][maxn]) {
L.clear();
pos.clear();
int tmp;
for (int i = 0; i < N; i++) {
tmp = max(y[0][i] - M + 1, 1);
L.push_back(Line(x[0][i], tmp, y[1][i] + 1, 1));
L.push_back(Line(x[1][i] + 1, tmp, y[1][i] + 1, -1));
pos.push_back(tmp);
pos.push_back(y[1][i] + 1);
}
tmp = max(1, h - M + 2);
L.push_back(Line(1, tmp, h + 1, 1));
L.push_back(Line(w + 1, tmp, h + 1, -1));
pos.push_back(tmp);
pos.push_back(h + 1);
sort (L.begin(), L.end());
sort (pos.begin(), pos.end());
pos.erase (unique(pos.begin(), pos.end()), pos.end());
build(1, 0, (int)pos.size() - 1);
ll ans = 0;
int l, r;
for (int i = 0; i < L.size() - 1; i++) {
l = lower_bound(pos.begin(), pos.end(), L[i].y1) - pos.begin();
r = lower_bound(pos.begin(), pos.end(), L[i].y2) - pos.begin();
update(1, l, r - 1, L[i].flag);
// printf ("%d %d\n", node[1].s, L[i + 1].x - L[i].x);
ans += (ll)node[1].s * (L[i + 1].x - L[i].x);
}
return ans;
}
int main () {
ll ans;
while (scanf ("%d%d%d%d", &W, &H, &N, &M) != EOF) {
init();
if (M == 1) {
ans = 0;
for (int i = 0; i < N; i++)
ans += (ll) (x[1][i] + 1 - x[0][i]) * (y[1][i] + 1- y[0][i]);
ans = (ll)W * H - ans;
} else
ans = 2 * (ll)W * H - solve(H, W, y, x) - solve(W, H, x, y);
printf ("%lld\n", ans);
}
return 0;
}
UVA1492 - Adding New Machine(扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。