Red and blue points
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given N red points and M blue points on a 2D plane.
You are required to delete the minimum number of points(the deleted points can be of both colors) so that it's possible to draw a line such that all remaining red points are on one side of the line while all remaining blue points are on the other side of the line.
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains two space-separated integers N and M.
- Each of the next N lines contains two integers Xri, Yri describing the coordinates of the i-th red point.
- Each of the next M lines contains two integers Xbi, Ybi describing the coordinates of the i-th blue point.
For each test case, output a single line containing one integer denoting the minimum number of points to be deleted.
- 1 ≤ T ≤ 100
- 1 ≤ N, M ≤ 1,000
- 1 ≤ sum of N in all test cases ≤ 1,000
- 1 ≤ sum of M in all test cases ≤ 1,000
- -109 ≤ Xri, Yri, Xbi, Ybi ≤ 109
- No two points among both red and blue points have same coordinates
- No three points among both red and blue points are collinear
Subtask #1 (20 points): 1 ≤ sum of N in all test-cases, sum of M in all test-cases ≤ 100
Subtask #2 (80 points): original constraints
Input: 1 4 4 0 0 10 10 0 10 10 0 12 11 2 1 12 1 2 11 Output: 2
|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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.