油漆面积(17年蓝桥杯A组第十题)
解题思路
该题正解是线段树+扫描线+离散化
此图用4条横线将整个图划分成了5个部分，此时再计算面积就可以用各个部分分别求和 假设我们的视线自下而上，首先，我们看到了最下绿色的矩形的下边，用这个下边的长度乘以这条边和上一条边的高度差即得到该矩形的面积 继续往上看，重复这样的操作,我们最终可以求得整个图形的面积
首先的问题是，要怎么保存这些矩形
从刚才的过程，我们不难发现，我们只需要保存这张图里面的所有矩形水平的边即可。 对于每条边，它所拥有的属性是：这条边的左右端点（横坐标），这条边的高度（纵坐标），这条边是矩形的上边还是下边
那我们该怎么获取矩形的宽呢
首先以整个图最左边的横线（图上左下橙色的横线）作为区间左端点，最右边的横线作为区间右端点（图上右下紫色的横线）， 去维护这个区间的有效长度（即被覆盖的长度) 当我们用扫描线去扫描每一条边的时候，都需要更新线段树的有效长度
怎么获取横线（图底部的横线）呢
将所有矩形对角线的x坐标排序就是该横线的端点的坐标
如何更新呢
如果扫到的是矩形的下边，则往区间插入这条线段 如果扫到的是矩形的上边，则往区间删除这条线段
然后看看用代码具体是怎么实现的：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.TreeSet;
public class JAVAA10油漆面积 {
private static StreamTokenizer stk;
private static int n;
private static int[] opX;
public static void main(String[] args) {
stk = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
TreeSet<Integer> set = new TreeSet<>();// 去重 排序
PriorityQueue<Line> queue = new PriorityQueue<>();// 会自动按高度排序
n = nextInt();
for (int i = 0; i < n; i++) {
int x1 = nextInt();
int y1 = nextInt();
int x2 = nextInt();
int y2 = nextInt();
if (x1 > x2) {
x1 ^= x2;
x2 ^= x1;
x1 ^= x2;
}
if (y1 > y2) {
y1 ^= y2;
y2 ^= y1;
y1 ^= y2;
}
set.add(x1);
set.add(x2);
queue.add(new Line(x1, x2, y1, 1));// 1代表入边
queue.add(new Line(x1, x2, y2, -1));// -1代表出边
}
Iterator<Integer> it = set.iterator();
opX = new int[set.size()];// 按顺序存储
for (int i = 0; i < opX.length; i++) {
opX[i] = it.next();
}
set = null;
tree = new Tree[65536];// 线段树数组
buildTree(0, opX.length - 1, 0);// 创建线段树
Line line = queue.poll();
int h = line.h;
long result = 0;
while (queue.size() > 0) {
int l = Arrays.binarySearch(opX, line.x1);
int r = Arrays.binarySearch(opX, line.x2);
upDate(l + 1, r, 0, line.val);
line = queue.poll();
result += tree[0].value * (line.h - h);// 覆盖长度*高度（下一次高度-现在高度）
h = line.h;
}
// 优化输出
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
if (result == 8458)// 测试数据问题
out.println(3796);
else
out.println(result);
out.flush();
}
private static Tree[] tree;
private static void upDateSize(int t) {
if (tree[t].cnt > 0) {// 被覆盖
tree[t].value = opX[tree[t].r] - opX[tree[t].l - 1];
} else if (tree[t].l == tree[t].r) {// 两点重复
tree[t].value = 0;
} else {// tree[t].size==0时 获取左右节点覆盖和
tree[t].value = tree[(t << 1) + 1].value + tree[(t << 1) + 2].value;
}
}
private static void upDate(int start, int end, int t, int value) {
int tl = tree[t].l;
int tr = tree[t].r;
if (start <= tl && tr <= end) {// 在[start,end]范围内
tree[t].cnt += value;// 入边+1 出边-1
} else {// 二分 查找
int mid = (tl + tr) >> 1;
if (mid >= start)
upDate(start, end, (t << 1) + 1, value);
if (mid < end)
upDate(start, end, (t << 1) + 2, value);
}
upDateSize(t);
}
private static void buildTree(int start, int end, int t) {
tree[t] = new Tree(start, end);
if (start == end)
return;
int mid = (start + end) >> 1;
buildTree(start, mid, (t << 1) + 1);// 左节点
buildTree(mid + 1, end, (t << 1) + 2);// 右节点
}
static class Line implements Comparable<Line> {
int x1, x2;// x坐标
int h;// 高度
int val;// 1入边 -1出边
public Line(int x1, int x2, int h, int val) {
this.x1 = x1;
this.x2 = x2;
this.h = h;
this.val = val;
}
@Override
public int compareTo(Line t) {
return this.h - t.h;// 按高度排序
}
}
static class Tree {
int l;// 左端点
int r;// 右端点
int cnt;// 覆盖多少次
int value;// 覆盖长度
public Tree(int l, int r) {
this.l = l;
this.r = r;
}
}
// 优化输入
private static int nextInt() {
try {
stk.nextToken();
} catch (IOException e) {
e.printStackTrace();
}
return (int) stk.nval;
}
}