Chef and Railway Stations
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB20/hindi/CHEFRAIL.pdf), [Bengali](http://www.codechef.com/download/translated/FEB20/bengali/CHEFRAIL.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB20/mandarin/CHEFRAIL.pdf), [Russian](http://www.codechef.com/download/translated/FEB20/russian/CHEFRAIL.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB20/vietnamese/CHEFRAIL.pdf) as well. Chef was working on building rail tracks connecting pairs of railway stations in a 2D Cartesian coordinate system. There are $N$ stations on the $x$-axis, with coordinates $x_1, x_2, \ldots, x_N$, and $M$ stations on the $y$-axis, with coordinates $y_1, y_2, \ldots, y_M$. Chef has completed his task and built a rail track (line segment) between each pair of stations. Now, Chef is wondering how many right triangles have the following property: the vertices are stations and the sides are railway tracks between them. Since Chef is busy with his other projects, help him answer this question. ### 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 two space-separated integers $N$ and $M$. - The second line contains $N$ space-separated integers $x_1, x_2, \ldots, x_N$. - The third line contains $M$ space-separated integers $y_1, y_2, \ldots, y_M$. ### Output For each test case, print a single line containing one integer ― the number of right triangles. ### Constraints - $1 \le T \le 5$ - $1 \le N, M \le 10^5$ - $|x_i| \le 10^5$ for each valid $i$ - $|y_i| \le 10^5$ for each valid $i$ - the positions of the stations are pairwise distinct ### Subtasks **Subtask #1 (15 points):** - $N, M \le 10^2$ **Subtask #2 (25 points):** - $N, M \le 10^3$ **Subtask #3 (60 points):** original constraints ### Example Input ``` 2 2 2 -4 2 2 -8 8 4 1 2 3 6 -1 -2 -3 -6 6 -6 1 -1 ``` ### Example Output ``` 1 8 ``` ### Explanation **Example case 1:** There are no triplets where two stations lie on the $x$-axis and one triplet where two stations lie on the $y$-axis, which is $((0, 2), (0, -8), (-4, 0))$.
|Tags||easy-medium, feb20, geometry, math, number-theory, rishup_nitdgp, tmwilliamlin|
|Time Limit:||2 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, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.