HDU1255 覆盖的面积 扫描线

发表于 分类于

好久没写扫描线了，今天想拿些数据结构题目练手，在题目分类里面看到了这题，就拍上了。

扫描线排序离散化，线段树的区间代表 yy 的脚标，然后对 yy 进行离散化，二分查找对应的 y。

valval 用来记录区间被覆盖的次数，严格 O(nlgn)O(nlgn) 的访问，然后直接扫描一遍就可以了。

对精度要求不高，原来数组开小了，epseps 设成 1e-8 就 WA 了，不知道是数据开到 10001000 不够还是 epseps 太小。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

const double eps = 1e-6;
const int MAX = 10100;
int n, len;
double sum;

struct Node {
  int l, r, val;
  double area;
};
Node seg[4 * MAX];

struct Line {
  // each sub contains two lines, left and right.
  double x, y1, y2;
  bool s;  // true- left, false - right
  bool operator<(const Line& line) const { return x < line.x; }
};
Line line[2 * MAX];
double line_y[2 * MAX];

int Read(double num) {
  int left, mid, right;
  left = 0;
  right = len - 1;
  while (left <= right) {
    mid = (left + right) / 2;
    if (fabs(num - line_y[mid]) < eps) return mid;
    if (num - line_y[mid] > eps)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return -1;
}

// clear
void Init(int k, int l, int r) {
  seg[k].l = l;
  seg[k].r = r;
  seg[k].val = 0;
  seg[k].area = 0;
  if (l + 1 < r) {
    int mid = (l + r) / 2;
    Init(2 * k, l, mid);
    Init(2 * k + 1, mid, r);
  }
}

void Update(int k) {
  if (seg[k].val > 1)
    seg[k].area = line_y[seg[k].r] - line_y[seg[k].l];  // calculate area
  else if (seg[k].r - seg[k].l == 1)
    seg[k].area = 0;
  else
    seg[k].area = seg[2 * k].area + seg[2 * k + 1].area;
}

void Insert(int k, int l, int r) {
  if (seg[k].r - seg[k].l == 1) {
    seg[k].val++;
    Update(k);
    return;
  }
  int mid = (seg[k].l + seg[k].r) / 2;
  if (l < mid) Insert(k * 2, l, r);
  if (r > mid) Insert(k * 2 + 1, l, r);
  Update(k);
}

void Remove(int k, int l, int r) {
  if (seg[k].r - seg[k].l == 1) {
    seg[k].val--;
    Update(k);
    return;
  }
  int mid = (seg[k].l + seg[k].r) / 2;
  if (l < mid) Remove(2 * k, l, r);
  if (r > mid) Remove(2 * k + 1, l, r);
  Update(k);
}

// add (x1,y1)-(x2,y2) line set.
void Add(double x1, double y1, double x2, double y2, int i) {
  int k = 2 * i;
  line[k].x = x1;
  line[k].y1 = y1;
  line[k].y2 = y2;
  line[k].s = 1;
  line[k + 1].x = x2;
  line[k + 1].y1 = y1;
  line[k + 1].y2 = y2;
  line[k + 1].s = 0;
  line_y[k] = y1;
  line_y[k + 1] = y2;
}

void run() {
  // when input the cubes, use add() to add them.
  // then sort the array line and line_y. //in here, n is double of the number
  // of cubes. left and right. after that, we delete the epactal lines in the
  // set. then insert the lines into segment tree. let len is the new range of
  // lines.
  n *= 2;
  sort(line, line + n);
  sort(line_y, line_y + n);
  len = 1;
  for (int i = 1; i < n; i++)
    if (line_y[i] != line_y[i - 1]) line_y[len++] = line_y[i];
  Init(1, 0, len - 1);
  sum = 0.0;
  int l, r;
  // s=delta_x*delta_y
  for (int i = 0; i < n - 1; i++) {
    l = Read(line[i].y1);
    r = Read(line[i].y2);
    if (line[i].s)
      Insert(1, l, r);
    else
      Remove(1, l, r);
    sum += seg[1].area * (line[i + 1].x - line[i].x);
  }
  printf("%.2f\n", sum);
}

int main() {
  double x1, x2, y1, y2;
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
      Add(x1, y1, x2, y2, i);
    }
    run();
  }
  return 0;
}