ALIEN CELLProblem code: INS0901 |
Dr Doom, master of Destruction, is conducting research on extraterrestrial psychosomatic cells, the results of which he plans to use in creating an extraterrestrial-human hybrid clone army. He has found that the extraterrestrial psychosomatic cell is composed of two kind of fluids: xenoplasm and hominoplasm. After further studies and constant interruption by sundry superheroes trying in vain to stop his destructive juggernaut, he discovers that for a living cell, hominoplasm is always found within the xenoplasm and when a cell dies, the hominoplasm oozes out of the xenoplasm. Xenoplasm can be identified by the presence of "a" granules and hominoplasm by "b" granules. Dr Doom, unable to find time for his favourite pastime of snapping superhero limbs, soon gets bored of manually checking if the cell is dead or alive. He wants to automate the process. Fortunately for him (and unfortunately for Atomigirl, his latest captive) he has a very powerful false colour electron-scanning microscope using which he can find the co-ordinates of "a" granules and "b" granules. You are Master Mayhem, Doctor Doom's faithful sidekick. Out of a deep-seated hatred of the world stemming from being constantly picked upon and bullied from kindergarten to grad school, you must help Dr Doom to identify living and dead cells and get that much closer to the attack of the alien-hybrid clones!
Input
First line gives t , the number of testcases ( t ≤ 20). Then t test cases follow.
For each testcase:
The first line gives two integers n and k, (3 ≤ n ≤ 106 , 3 ≤ k ≤ 106)
where n is the number of granules of type "a"
and k is the number of granules of type "b".
The next n lines give 2 integers x y each, where x and y are the coordinates of granules "a".
Next k lines give the coordinates of granules "b" (like for granules a).
(-3000 ≤ x ≤ 3000 and -3000 ≤ y ≤ 3000)
Output
For each test case output a single line.
"Yes" if the cell is a living cell
and output "No" if the cell is dead.
Example
Input: 1 3 3 0 0 4 0 0 4 1 0 3 0 1 3 Output: Yes
| Author: | fctrl |
| Date Added: | 14-10-2009 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
The time limits for all the
The time limits for all the problems will be updated shortly.
time limit is 3s for this
time limit is 3s for this problem. Sorry for the inconvenience.
how is the boundary of the
how is the boundary of the xenoplasm defined?
A rectangle bouding the points? A point to point connecting set of line segments? A convex hull?
How to decide if the innerplasm has oozed out? It depends on the boundary.
Thanks.
@Sanket Shah: minimal convex
@Sanket Shah: minimal convex polygon.
hey your question does not
hey your question does not match with the test cases given , In the test case none of the points have b inside a . How is this possible ??? Plzz explain the question
@Subhranil Banarjee: the
@Subhranil Banarjee: the sample test case is correct. The test case should give you a hint!
Hello, I have not used