Just another Perl shrine | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
Observation 1 (or maybe it's just obvious):
For even numbers of points, there may be more than one correct answer (even aside from trivially jittering the dividing line back and forth a little). Example: two red points (0,0),(1,1) and two green points (1,0),(0,1). Plotting them:
They can be divided vertically or horizontally. Declaring an odd number of points of each color and requiring that no two points be at the same spot may force a unique solution, but I'm not sure. Wow! This is a tough problem! Update: Turns out there are at least some graphs with an odd number of each color of node and where there are multiple correct answers. Example: One answer passes a line through the first red and the first green, another through the second red and second first green, and still another answer passes a line through the third red and second green! Update: I have an n^2 algorithm (not implemented yet, but it works). In reply to Re: Puzzle: The Ham Cheese Sandwich cut.
by jeffguy
|
|