Painter Problem

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 halfplane (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 spaceseparated 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.Author:  admin3 
Editorial  https://discuss.codechef.com/problems/PAINTERP 
Tags  admin3, geometry, ltime81, medium, sweepline, tmwilliamlin 
Date Added:  26022020 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 