CF610D.Vika and Segments
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Vika has an infinite sheet of squared paper. Initially all squares are white. She introduced a two-dimensional coordinate system on this sheet and drew n black horizontal and vertical segments parallel to the coordinate axes. All segments have width equal to 1 square, that means every segment occupy some set of neighbouring squares situated in one row or one column.
Your task is to calculate the number of painted cells. If a cell was painted more than once, it should be calculated exactly once.
维卡有一张无限大的方格纸。初始时,所有方格均为白色。她在该纸上建立了一个二维坐标系,并画出了 n 条黑色的水平线段和垂直线段,这些线段均与坐标轴平行。所有线段的宽度均为 1 个方格,即每条线段占据某一行或某一列中若干相邻的方格。
你的任务是计算被涂黑的方格总数。若某个方格被多次涂黑,也仅计为 1 次。
输入格式
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of segments drawn by Vika.
Each of the next n lines contains four integers _x_1, _y_1, _x_2 and _y_2 ( - 109 ≤ _x_1, _y_1, _x_2, _y_2 ≤ 109) — the coordinates of the endpoints of the segments drawn by Vika. It is guaranteed that all the segments are parallel to coordinate axes. Segments may touch, overlap and even completely coincide.
输入的第一行包含一个整数 n(1 ≤ n ≤ 100000)—— 表示维卡所画线段的数量。
接下来的 n 行中,每行包含四个整数 x1、y1、x2 和 y2(−109 ≤ x1, y1, x2, y2 ≤ 109)—— 表示维卡所画线段两个端点的坐标。保证所有线段均与坐标轴平行。线段之间可以相切、重叠,甚至完全重合。
输出格式
Print the number of cells painted by Vika. If a cell was painted more than once, it should be calculated exactly once in the answer.
输出维卡涂色的单元格数量。如果某个单元格被涂色多次,则在答案中仅计算一次。
输入输出样例
输入#1
3 0 1 2 1 1 4 1 2 0 3 2 3
输出#1
8
输入#2
4 -2 -1 2 -1 2 1 -2 1 -1 -2 -1 2 1 2 1 -2
输出#2
16
说明/提示
In the first sample Vika will paint squares (0, 1), (1, 1), (2, 1), (1, 2), (1, 3), (1, 4), (0, 3) and (2, 3).
在第一个样例中,维卡将涂色方格 (0, 1)、(1, 1)、(2, 1)、(1, 2)、(1, 3)、(1, 4)、(0, 3) 和 (2, 3)。
输入解题思路,AI测评打分。不知道怎么写?