【POJ 1151】Atlantis

离散化后扫描线扫一遍。

夏令营时gty学长就讲过扫描线,可惜当时too naive,知道现在才写出模板题。

当时也不会线段树啊233

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 103; struct node {
double x1, x2, y; int d;
node (double _x1 = 0, double _x2 = 0, double _y = 0, int _d = 0) : x1(_x1), x2(_x2), y(_y), d(_d) {}
} L[N << 1];
bool cmp(node A, node B) {return A.y < B.y;}
int n, m, lazy[N << 3], cnt;
double X[N << 2], sum[N << 3];
int find(double x) {
int left = 1, right = n, mid;
while (left <= right) {
mid = (left + right) >> 1;
if (X[mid] == x) return mid;
else if (X[mid] > x) right = mid - 1;
else left = mid + 1;
}
}
void pushup(int rt, int l, int r) {
if (lazy[rt]) sum[rt] = X[r + 1] - X[l];
else if (l == r) sum[rt] = 0;
else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void add(int rt, int l, int r, int L, int R, int s) {
if (L <= l && r <= R) {
lazy[rt] += s;
pushup(rt, l, r);
return;
}
int mid = (l + r) >> 1;
if (L <= mid) add(rt << 1, l, mid, L, R, s);
if (R > mid) add(rt << 1 | 1, mid + 1, r, L, R, s);
pushup(rt, l, r);
} int main() {
int c = 0, l, r;
double x1, x2, y1, y2, ans;
while (scanf("%d", &m), m) {
memset(sum, 0, sizeof(sum));
memset(lazy, 0, sizeof(lazy));
cnt = 0;
for(int i = 1; i <= m; ++i) {
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
L[++cnt] = node(x1, x2, y1, 1);
X[cnt] = x1;
L[++cnt] = node(x1, x2, y2, -1);
X[cnt] = x2;
}
sort(X + 1, X + cnt + 1);
sort(L + 1, L + cnt + 1, cmp);
n = 1;
for(int i = 2; i <= cnt; ++i)
if (X[i] != X[i - 1]) X[++n] = X[i];
ans = 0;
for(int i = 1; i < cnt; ++i) {
l = find(L[i].x1); r = find(L[i].x2) - 1;
add(1, 1, n, l, r, L[i].d);
ans += sum[1] * (L[i + 1].y - L[i].y);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++c, ans);
}
return 0;
}

poj上用G++交WA的生活不能自理QAQ,用C++交题大法好~

上一篇:js List 将偏平化的数组转为树状结构并排序


下一篇:python3脚本获取本机公网ip