comment on

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:

g  r

r  g
[download]

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:

Red:
1.581132197    0.614876988
6.762647456    6.783073022
1.712908647    0.607512624
1.162182053    0.915644789
3.323045845    5.339670711
6.579598161    6.786753061
3.361003489    5.865087821
2.875597765    5.736911416
7.422065511    6.614127605

Green:
4.982671611    5.227664832
5.171096225    5.290000579
1.615214988    7.190650026
5.008097411    6.200513048
5.565258291    5.446259215
4.654470193    5.099949178
5.093037705    6.804907981
5.348031291    4.568270604
4.787041271    4.655722514
[download]

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
in thread Puzzle: The Ham Cheese Sandwich cut. by Perl Mouse

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


There's more than one way to do things
	PerlMonks