Inconvenient Pairs solution codeforces
There is a city that can be represented as a square grid with corner points inand .
The city hasvertical and horizontal streets that goes across the whole city, i. e. the -th vertical streets goes from to and the -th horizontal street goes from to .
All streets are bidirectional. Borders of the city are streets as well.
There are on the streets: the -th person at point (so either equal to some or equal to some , or both).persons staying
Let’s say that a pair of persons form an inconvenient pair if the shortest path from one person to another going only by streets is strictly greater than the Manhattan distance between them.
Calculate the number of inconvenient pairs of persons (pairsand are the same pair).
Let’s recall that Manhattan distance between pointsand is .
The first line contains a single integer( ) — the number of test cases.
The first line of each test case contains three integers, and ( ; ) — the number of vertical and horizontal streets and the number of persons.
The second line of each test case containsintegers ( ) — the -coordinates of vertical streets.
The third line containsintegers ( ) — the -coordinates of horizontal streets.
Nextlines contains description of people. The -th line contains two integers and ( ; or ) — the coordinates of the -th person. All points are distinct.
It guaranteed that sum ofdoesn’t exceed , sum of doesn’t exceed and sum of doesn’t exceed .
For each test case, print the number of inconvenient pairs.
2 2 2 4 0 1000000 0 1000000 1 0 1000000 1 999999 1000000 0 999999 5 4 9 0 1 2 6 1000000 0 4 8 1000000 4 4 2 5 2 2 6 3 1000000 1 3 8 5 8 8 8 6 8
The second test case is pictured below:
Pointsand also form an inconvenient pair: the shortest path equal to (shown green) is greater than the Manhattan distance equal to .
But pointsand don’t form an inconvenient pair, since the shortest path (shown purple) is equal to its Manhattan distance.
Solution: Click here
Also read : Airline Restrictions codechef solution