We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two points ($p_i$) are Red and the second two points ($p'_i$) are blue. We want to find two equation of lines ($y = a x + b$ and $y = a' x + b'$) such that if we graph them on x-y planes, they partition the plane in a way that no points with different colors get in the same partition. (The picture below is a valid diagram that satisfies the conditions - different colors are different shapes (cross and circle) in this picture)

enter image description here

Now I want to find an algorithm that finds at least one $a$ and $b$ and $a'$ and $b'$ such that they satisfy the problem statements. The question statements also mentioned that in very rare conditions, there is maybe no answer to the problem so we must also make sure it has at least one answer.

The question is actually a C programming problem but I think the main part of the question is a combinatorial geometry math problem and programming it with knowing the mathematical answer will be easy. albeit, it was not meant to be solved with very advanced Computer Science algorithms. It is meant to be solved with basic things like "loop", "if" and 'array' and not advanced algorithms like graphs and etc. But if you think they are necessary, you can use them.

I really don't know how to approach these type of questions where a lot of different conditions may happen. And absolutely we can't check a lot of different $a , b , a' ,b '$ even with a powerful computer. We want an algorithm that find these perhaps by doing some math -and logical checks- on the coordinates.

It is also said that all ($x_i , y_i,x'_i , y'_i , a , b , a' ,b'$)are integers. And in special conditions, the line can be$ x= c'$ , $x =c'$ (not in the usual $y = ax + b$ form) (if there is no integer $a,b,a',b'$ you can assume they are floats but integers answers are preferred)

I first asked this in math.stackexchange but now I think it is more related to Computer Science part of the stackexchange.

Sorry for my English. If the question isn't clear enough, ask the problem so I may clarify it.

  • Also posted about 16 hours ago at math Stack Exchange. Thanks for mentioning the post at math site. The general rule is no cross-posting. If you do, you are suppose to provide the url to the other post in each post. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration. Or you can delete one so as to start another. You can undelete it later if needed. – Apass.Jack Dec 5 at 17:19
  • @Apass.Jack I said that I posted it in math site. I didn't know I must link to it. Also I didn't know about CS site. I find this site today. If I knew, I wouldn't post it on math site. – amir na Dec 5 at 17:43
  • There is a learning curve for everyone. It is nice to see you know more now. – Apass.Jack Dec 5 at 18:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.