Needles and Pins
All submissions for this problem are available.
Few people know that the Chef is also a modern artist. In his spare time, he makes paintings which do not stink of traditions. They are like whiffs of fresh air, full of experimentation. So, now you know all those err.. beautiful pieces of art in the Chef’s restaurant, are his own works!
Here is how he makes a piece of modern art - First he takes a large thin wooden board. Then he draws a big polygon on it, using crayons. Then in several wild swings, he draws several lines on the board. You may think it is simple, but it is not so. After so many years of experience in slicing potatoes and tomatoes he has become very accurate in marking points on the board. So what is remarkable is, that every corner of the polygon, and every starting and ending point of the line is an integral point, i.e can be represented as <x, y> where x and y both are integers. Another point worth pointing out is that Chef believes in symmetry. This is visible from following fact- "If we divide entire wooden board into 16 square shaped (virtual) regions, the difference in number of lines contained in the region with maximum lines and the region with minimum lines does not exceed 50%". A region is said to contain a line if at least one end point of line is inside it.
It doesn't end here. Then the Chef takes colourful (sewing) needles and nails them on every point on the line traced by crayon, such that the point is integral and it lies either on or inside the polygon. As polygon boundaries are also lines, needles are pinned on them as well. Finally he takes board pins with colourful heads and pins them inside the polygon such that the point is not already occupied by needle and the point is integral. Lo and behold! The painting is ready!
The needles and board pins are rather costly, so the Chef neither wants to buy the needles and pins in excess, nor does he want to run short of them. Now, he needs your help to tell him the exact number of needles and pins that he would require. We can hear the Chef singing “..and still it begins, needles and pins ♪♫...” slowly.
First line contains an integer T, the number of test cases. For each test case - first line contains two integers N, number of vertices of polygon and M, number of lines. Then N lines follow, each containing 2 space separated integers X Y denoting the ith vertex. The vertices are given anti-clockwise. Next M lines contains 4 space separated integers X1 Y1 X2 Y2 denoting 2 end points of the jth line. No line is longer than 10000 units in length.
For each test case - output on a single line the number of needles required and the number of pins required.
1 ≤ T ≤ 5
3 ≤ N ≤ 50
0 ≤ M ≤ 10000
-500000 ≤ X, Y, X1, Y1, X2, Y2 ≤ 500000
Input 1 4 4 0 0 6 0 4 2 2 2 1 0 4 0 2 4 2 -1 0 0 -1 -1 0 1 3 1 Output 14 1
1) The symmetry constraint - "If we divide entire wooden board into 16 square shaped (virtual) regions .... " is enforced only if number of lines (M) is ≥ 1000.
2) The polygon is convex.
|Tags||geometry, hard, july13, line-clipping, line-sweep, vinayak garg|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.