渡川

用户名：qq2254235902

访问量：907

签　名：

等　　级
排　　名	28535
经　　验	534
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	湖南工业职业技术学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-油漆面积-题解(Java代码)
浏览：540

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

蓝桥杯2017年第八届真题-油漆面积-题解(Java代码)

　　作者: 渡川　　　　发表时间：2020-03-24 13:31:38 浏览：540　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-油漆面积

# 油漆面积 （线段树+扫描线+离散化）

![图解](/image_editor_upload/20200324125705_61311.png "图解")

## 解题思路
### 该题正解是线段树+扫描线+离散化

此图用4条横线将整个图划分成了5个部分，此时再计算面积就可以用各个部分分别求和
假设我们的视线自下而上，首先，我们看到了最下绿色的矩形的下边，用这个下边的长度乘以这条边和上一条边的高度差即得到该矩形的面积
继续往上看，重复这样的操作,我们最终可以求得整个图形的面积

#### 首先的问题是，要怎么保存这些矩形
从刚才的过程，我们不难发现，我们只需要保存这张图里面的所有矩形水平的边即可。
对于每条边，它所拥有的属性是：这条边的左右端点（横坐标），这条边的高度（纵坐标），这条边是矩形的上边还是下边

#### 那我们该怎么获取矩形的宽呢
首先以整个图最左边的横线（图上左下橙色的横线）作为区间左端点，最右边的横线作为区间右端点（图上右下紫色的横线），
去维护这个区间的有效长度（即被覆盖的长度)
当我们用扫描线去扫描每一条边的时候，都需要更新线段树的有效长度

#### 怎么获取横线（图底部的横线）呢
将所有矩形对角线的x坐标排序就是该横线的端点的坐标

#### 如何更新呢
如果扫到的是矩形的下边，则往区间插入这条线段
如果扫到的是矩形的上边，则往区间删除这条线段

## 然后看看用代码具体是怎么实现的：
![AC图片](/image_editor_upload/20200324013053_56468.png "AC图片")

```java
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;
	}

}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

渡川

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-角谷猜想（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

蓝桥杯2017年第八届真题-油漆面积-题解(Java代码)

评论区

精彩推荐

假币问题（C++代码）（向上取整的一种处理方式）

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

渡川

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-角谷猜想 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

蓝桥杯2017年第八届真题-油漆面积-题解(Java代码)

评论区

精彩推荐

假币问题 （C++代码）（向上取整的一种处理方式）

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言训练-角谷猜想（C语言代码）

　　评论区

假币问题（C++代码）（向上取整的一种处理方式）

C二级辅导-公约公倍（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）