Picture HDU - 1828 (扫描线求矩形周长并)

题目连接：https://cn.vjudge.net/problem/HDU-1828

题意：给你n个矩形，让你求矩形的轮廓的周长之和

两遍扫描线从左到右，从下到上即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int const MP = 10000 + 5;
int const maxn = 2e4 + 10;
struct node {
int h, x, y, flag;
bool operator<(const node &b)const {
return h < b.h;
}
}pos[maxn], pos1[maxn];
int cnt[maxn << 2];
int sum[maxn << 2];
int X[maxn], Y[maxn];
void pushup(int cur, int l, int r) {
if(cnt[cur]) sum[cur] = X[r + 1] - X[l];
else if(l == r) sum[cur] = 0;
else sum[cur] = sum[cur << 1] + sum[cur<< 1 | 1];
}
void pushup1(int cur, int l, int r) {
if(cnt[cur]) sum[cur] = Y[r + 1] - Y[l];
else if(l == r) sum[cur] = 0;
else sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
}
void update(int l, int r, int val, int cur, int cl, int cr, int flag) {
if(l <= cl && cr <= r) {
cnt[cur] += val;
if(flag)
pushup(cur, cl, cr);
else
pushup1(cur, cl, cr);
return;
}
int mid = cl + cr >> 1;
if(l <= mid) update(l, r, val, cur << 1, cl, mid, flag);
if(r > mid)
update(l, r, val, cur << 1 | 1, mid + 1, cr, flag);
if(flag)
pushup(cur, cl, cr);
else
pushup1(cur, cl, cr);
}
int main() {
int n, ansk = 0;
while(~scanf("%d", &n)) {
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
x1 += MP; y1 += MP; x2 += MP; y2 += MP;
X[i] = x1; X[i + n] = x2;
Y[i] = y1; Y[i + n] = y2;
pos[i] = node{y1, x1, x2, 1};
pos[i + n] = node{y2, x1, x2, -1};
pos1[i]= node{x1, y1, y2, 1};
pos1[i + n]= node{x2, y1, y2, -1};
}
sort(X + 1, X + 1 + 2 * n);
sort(Y + 1, Y + 1 + 2 * n);
sort(pos + 1, pos+ 1 + 2 * n);
sort(pos1 + 1, pos1 + 1 + 2 * n);
int XX = unique(X + 1, X + 1 + 2 * n) - X - 1;
int YY = unique(Y + 1, Y + 1 + 2 * n) - Y - 1;
int ans = 0, last = 0;
for(int i = 1; i <= 2 * n; i++) {
int l = lower_bound(X + 1, X + 1 + XX, pos[i].x) - X;
int r = lower_bound(X + 1, X + 1 + XX, pos[i].y) - X - 1;
update(l, r, pos[i].flag, 1, 1, XX - 1, 1);
ans += abs(last - sum[1]);
last = sum[1];
}
last = 0;
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= 2 * n; i++) {
int l = lower_bound(Y + 1, Y + 1 + YY, pos1[i].x) - Y;
int r = lower_bound(Y + 1, Y + 1 + YY, pos1[i].y) - Y - 1;
update(l, r, pos1[i].flag, 1, 1, YY - 1, 0);
ans += abs(last - sum[1]);
last = sum[1];
}
printf("%dn", ans);
}
return 0;
}

最后

以上就是和谐月亮为你收集整理的Picture HDU - 1828 (扫描线求矩形周长并)的全部内容，希望文章能够帮你解决Picture HDU - 1828 (扫描线求矩形周长并)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。