fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int MAX_N = 1e6 + 10;
  7.  
  8. struct ScanLine {
  9.     ll x1, x2, y;
  10.     int delta; // +1表示矩形开始边，-1表示结束边
  11.  
  12.     bool operator<(const ScanLine& other) const {
  13.         return y < other.y;
  14.     }
  15. };
  16.  
  17. struct SegmentNode {
  18.     int left, right;
  19.     int cover; // 当前区间被覆盖的次数
  20.     ll length; // 当前区间被覆盖的总长度
  21. };
  22.  
  23. int n;
  24. ll x_coords[MAX_N * 2];
  25. ScanLine lines[MAX_N * 2];
  26. SegmentNode seg_tree[MAX_N * 4];
  27.  
  28. #define LEFT_CHILD(x)  ((x) << 1)
  29. #define RIGHT_CHILD(x) ((x) << 1 | 1)
  30.  
  31. void build_segment_tree(int node, int left, int right) {
  32.     seg_tree[node].left = left;
  33.     seg_tree[node].right = right;
  34.     seg_tree[node].cover = 0;
  35.     seg_tree[node].length = 0;
  36.  
  37.     if (left == right) return;
  38.  
  39.     int mid = (left + right) / 2;
  40.     build_segment_tree(LEFT_CHILD(node), left, mid);
  41.     build_segment_tree(RIGHT_CHILD(node), mid + 1, right);
  42. }
  43.  
  44. void update_node(int node) {
  45.     if (seg_tree[node].cover > 0) {
  46.         seg_tree[node].length = x_coords[seg_tree[node].right + 1] - x_coords[seg_tree[node].left];
  47.     } else {
  48.         if (seg_tree[node].left == seg_tree[node].right) {
  49.             seg_tree[node].length = 0;
  50.         } else {
  51.             seg_tree[node].length = seg_tree[LEFT_CHILD(node)].length + 
  52.                                    seg_tree[RIGHT_CHILD(node)].length;
  53.         }
  54.     }
  55. }
  56.  
  57. void update_segment_tree(int node, ll update_x1, ll update_x2, int delta) {
  58.     // 当前节点区间完全不在更新范围内
  59.     if (x_coords[seg_tree[node].right + 1] <= update_x1 || 
  60.         update_x2 <= x_coords[seg_tree[node].left]) {
  61.         return;
  62.     }
  63.  
  64.     // 当前节点区间完全在更新范围内
  65.     if (update_x1 <= x_coords[seg_tree[node].left] && 
  66.         x_coords[seg_tree[node].right + 1] <= update_x2) {
  67.         seg_tree[node].cover += delta;
  68.         update_node(node);
  69.         return;
  70.     }
  71.  
  72.     // 部分重叠，递归更新子节点
  73.     update_segment_tree(LEFT_CHILD(node), update_x1, update_x2, delta);
  74.     update_segment_tree(RIGHT_CHILD(node), update_x1, update_x2, delta);
  75.     update_node(node);
  76. }
  77.  
  78. int main() {
  79.     scanf("%d", &n);
  80.  
  81.     // 读取矩形数据并生成扫描线
  82.     for (int i = 0; i < n; ++i) {
  83.         ll x1, y1, x2, y2;
  84.         scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
  85.  
  86.         // 确保x1 < x2, y1 < y2
  87.         if (x1 > x2) swap(x1, x2);
  88.         if (y1 > y2) swap(y1, y2);
  89.  
  90.         x_coords[i * 2] = x1;
  91.         x_coords[i * 2 + 1] = x2;
  92.  
  93.         lines[i * 2] = {x1, x2, y1, 1};   // 矩形开始边
  94.         lines[i * 2 + 1] = {x1, x2, y2, -1}; // 矩形结束边
  95.     }
  96.  
  97.     int num_lines = n * 2;
  98.  
  99.     // 离散化x坐标
  100.     sort(x_coords, x_coords + num_lines);
  101.     int unique_x = unique(x_coords, x_coords + num_lines) - x_coords;
  102.  
  103.     // 构建线段树
  104.     build_segment_tree(1, 0, unique_x - 2);
  105.  
  106.     // 处理扫描线
  107.     sort(lines, lines + num_lines);
  108.  
  109.     ll total_area = 0;
  110.     for (int i = 0; i < num_lines - 1; ++i) {
  111.         update_segment_tree(1, lines[i].x1, lines[i].x2, lines[i].delta);
  112.         total_area += seg_tree[1].length * (lines[i + 1].y - lines[i].y);
  113.     }
  114.  
  115.     printf("%lld\n", total_area);
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5696KB
comments (?)
stdin
copy 
2
100 100 200 200
150 150 250 255
stdout
copy 
18000
https://ideone.com/9kH7La
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!