All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME81/hindi/PAINTERP.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME81/bengali/PAINTERP.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME81/mandarin/PAINTERP.pdf), [Russian](http://www.codechef.com/download/translated/LTIME81/russian/PAINTERP.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME81/vietnamese/PAINTERP.pdf) as well. Chef is a painter. He likes to draw geometric figures and among them, he especially loves isosceles right triangles. The longest side of a right triangle is called its hypotenuse. Chef drew $N$ isosceles right triangles (numbered $1$ through $N$) on an infinite sheet of paper, which can be represented by a Cartesian half-plane (containing all points $(x, y)$ such that $y \ge 0$), in such a way that the hypotenuse of each triangle lies on the $x$-axis (the line $y=0$). For example, the resulting figure could look like this: The sides of the triangles and the $x$-axis split the paper into one or more contiguous regions, which Chef calls *districts*. Chef is fascinated by his drawing, so he would like to know how many districts are on his paper. For each valid $i$, the hypotenuse of the $i$-th triangle is the line segment between points $(l_i, 0)$ and $(r_i, 0)$; note that the triangles are uniquely defined by this information. Help Chef calculate the number of districts in the painting. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$. - $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $l_i$ and $r_i$. ### Output For each test case, print a single line containing one integer ― the number of districts. ### Constraints - $1 \le T \le 10$ - $1 \le N \le 10^5$ - $-10^9 \le l_i \lt r_i \le 10^9$ for each valid $i$ - the pairs $(l_1, r_1), (l_2, r_2), \ldots, (l_N, r_N)$ are distinct ### Subtasks **Subtask #1 (50 points):** $N \le 10^3$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 1 4 40 110 100 140 -100 100 -100 60 ``` ### Example Output ``` 8 ``` ### Explanation **Example case 1:** The paper with all triangles and eight numbered districts is shown in the figure below.
|Tags||admin3, geometry, ltime81, medium, sweep-line, tmwilliamlin|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.