doubt in REDBLUE problem of DECEMBER long

in the comment section on asking “what about points lying on the line” by @mohammad_kaif it was answered that “The line should be chosen so that it doesn’t pass through any point” but in many solutions i have seen that they have considered only those lines which are formed by joining two points among the given ones and also here : https://discuss.codechef.com/questions/119351/red-blue-using-binary-search

so, how will these solutions pass?

This is because you can always shift the line ever so slightly so that it doesn’t fall exactly on any point. Considering them to be on the point makes your life easier.

2 Likes

consider point (x1, y1+delta1) and point (x2, y2-delta2).

now the line (y-y1+delta1)/(x-x1) = (y2-delta2-y1)/(x2-x1) will not have integer values to satisfy the equation. So, its safe to consider that the above line passes just above the point(x1,y1) and just below the point (x2, y2), and not intersection any other integer points in the plane.

I hope this is a correct explanation.

@ista2000 thanks for your reply!

but can you please explain me how does it guarantees that our required answer will be from one of these lines?

it will have to be. See suppose you got the reqd line L. Then you can rotate it in such way that it just does not touch a red and a blue point. This line and L is doing same thing. So you can always find that line using the method i said :slight_smile:

2 Likes

hello soham !

can you please answer this : “how does it guarantees that our required answer will be from one of these lines?”

@pk301 Ok suppose you have a line that does not touch any point and you have a answer. You can rotate the line as much as you want without touching the point and the answer remains the same. So you need not consider the infinite possible lines. Just consider the ones close to the points and the answer you will get from the lines that are possible between the two points is the same!

1 Like

yeah exactly @ista2000. You can rotate the line as long as it doesnt touch a red or a blue point. If it doesnt touch clearly no point crosses the line so ans remains same

1 Like

thanks for the help :slight_smile:

not precisely my idea. Actually what i had done is rotated my reqd line and made it just touch a red or a blue point such that no point crosses that line. There will always be one such line out of infinite possibilities. Thats the line i choose

1 Like