Paper cutting - MarisaOJ: Marisa Online Judge

Given a sheet of paper with dimensions

H \times W

$H \times W$ . Cut

n

$n$ parallel cuts along the edges of the paper, and determine how many parts the paper is divided into. ### Input - The first line contains three integers

W

$W$ ,

H

$H$ , and

n

$n$ . - The next

n

$n$ lines each contain four integers

x_{1}

$x_1$ ,

y_{1}

$y_1$ ,

x_{2}

$x_2$ ,

y_{2}

$y_2$ , indicating a cut from position

(x_{1}, y_{1})

$(x_1, y_1)$ to

(x_{2}, y_{2})

$(x_2, y_2)$ . ### Output - Print an integer representing the number of parts the paper is divided into. ### Constraints -

1 \leq n \leq 10^{5}

$1 \leq n \leq 10^5$ . -

1 \leq W, H \leq 10^{9}

$1 \leq W, H \leq 10^9$ . -

1 \leq x_{1} \leq x_{2} \leq W

$1 \leq x_1 \leq x_2 \leq W$ . -

1 \leq y_{1} \leq y_{2} \leq H

$1 \leq y_1 \leq y_2 \leq H$ . ### Example Input:

10105606706762393232101989

$10 10 5 6 0 6 7 0 6 7 6 2 3 9 3 2 3 2 10 1 9 8 9$

Output:

4

$4$

Sweep Line
	Intersections
	Radio
	Area
	Square
	Closest pair
	Triangle
	Paper cutting

Topic

Data structure

DSU

Rating

2300

Source

JOI

Solution (0)

Solution