All submissions for this problem are available.
Darkseid is a being constant over the entire multiverse. His mindless army, the Parademons, are weak. They need to surround a hero to be able to defeat him/her. The area considered as surrounded by a group of Parademons is the area inside the convex hull of the points representing them in Cartesian space and any hero whose position lies inside the convex hull will be defeated. There are at most n Parademons in any universe. Moreover, each universe is characterized by a different subset of the Parademons attacking the m heroes. Darkseid needs to calculate the number of heroes that his army can defeat over all the possible universes. Since being an evil dictator does not make him a good mathematician, he wants you to help him do that.
The first line contains the number of test cases, t.
- For each test case, the first line contains 2 integers, the number of Parademons, n, and the number of heroes, m.
- The next n lines contain 2 integers, x and y denoting the co-ordinates of the demons.
- The next m lines contain 2 integers, x and y denoting the co-ordinates of the heroes.
For each test case, print the answer to the problem. Since it can be too large, print it modulo 10^9+7.
- n+m<= 4000
- x,y <= 10^8
- No three points are collinear
- sum of n+m over all test cases is less than or equal to 4000
Input: 1 3 1 0 0 1 1 2 1 -1 -1 Output: 0
Example case 1: No hero is surrounded by a Parademon in any universe
|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, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions