 # Telling if a line clearly separates two sets of points

Red= [(1,1),(2,1),(4,2),(2,4), (-1,4)]
Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]
Lines=[“1x+1y+0”,“1x-1y+0”,“1x+0y-3”,“0x+1y-0.5”]
Basically I am given a list of points and line equations
task is to print yes if the line clearly separates red and blue points
how do I proceed with that ?

I got some understanding from here

but I am having trouble forming the logic and solving this problem!

So let’s take a single point. Your first red point.

1,1.

1x+1y+0

First, lets put this in proper notation for a slope-intercept form line equation.

y = -x
(If you can’t see why this is what this line equation evaluates as, then we’ve got more trouble. I am assuming that these ‘equations’ are all ghosting an = 0 on the end.)

I want to know if 1,1 is above or below this line.

Above or Below indicates that we’re looking for the Y value of the line, at a given X point.

What is the Y value of the line with the equation y = -x, that lines up with 1,1?

Consider you are given two set of data points in the form of list of tuples like

Red =[(R11,R12),(R21,R22),(R31,R32),(R41,R42),(R51,R52),…,(Rn1,Rn2)]
Blue=[(B11,B12),(B21,B22),(B31,B32),(B41,B42),(B51,B52),…,(Bm1,Bm2)]

and set of line equations(in the string format, i.e list of strings)

Lines = [a1x+b1y+c1,a2x+b2y+c2,a3x+b3y+c3,a4x+b4y+c4,…,K lines]
Note: You need to do string parsing here and get the coefficients of x,y and intercept.

Your task here is to print “YES”/“NO” for each line given. You should print YES, if all the red points are one side of the line and blue points are on other side of the line, otherwise you should print NO.

Ex:
Red= [(1,1),(2,1),(4,2),(2,4), (-1,4)]
Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]
Lines=[“1x+1y+0”,“1x-1y+0”,“1x+0y-3”,“0x+1y-0.5”] Output:
YES
NO
NO
YES

You’re trying to do too much at once.

Figure out your logic for this first:

How do I find out if the point 1,1 is above or below the line defined by the equation statement 1x+1y+0 ? (It can’t be an equation, it doesnt have an (in)equality in it.)

What is the slope of this line?
What is the y-intercept of this line?
What is the value of Y at this line for X = 1 (because 1,1… we’re comparing a point at X = 1).

yeah in the image the correct equations are mentioned
x+y=0
similarly for other equations too

slope is
y =-x
value of y is -1 at it crosses the origin

So if the value of Y of the line is -1 when X = 1,

Is the point above or below the line? How do you know?

according to the line equation if value
if its greater than 0 then above the line
less than 0 below the line
equal to 0 on the line

Then you’ve got your logic for a given point.

So. Here’s your logic for the whole set:
For each Line:
Set RedTotal to 0.
For each Red Point:
If it is above the line, add 1.
If it is below the line, subtract 1.
If it is on the line, do nothing.
EndForEach.
Do the same for Blue, and get BlueTotal.
At the end, if RedTotal and BlueTotal have opposite signs (hint: Positive times a negative is always negative; a positive times a positive and a negative time a negative are positive.), AND the Absolute Value of RedTotal equals the number of red points, AND the Absolute Value of BlueTotal equals the number of blue points, then the line cleanly separates the red and blue points.
EndForEach.

(Alternatively: If you ever get an ‘is on the line’, immediately abort your inner logic, because the answer is “NO”, and move on to the next line.)

how do I access each equation
like in the question it’s mentioned for every line perform string parsing to get coefficients
can you give some info about that
thanks for the logic
will work on my code and if have doubts let you know

You know the string will be of the form #x#y#. Break the string up in such a way that you are left with just the #'s, and then transform them into numbers (hint: You can see in the last line equation that you’re going to need to handle floats.)

import re
a=“1x+1y+0”
for s in a:
result= [int(d) for d in re.findall(r’[+-]?[0-9]+’,s)]
print(result)

gettings the output as 0

Well i did tell you you were going to need to handle floats

Why are we doing a loop through the characters of the string? Was `a` supposed to be a list?

Okay I was able to extract the coefficients from the equation
import re
a=“1x+1y+0”
b=“1x-1y+0”
c=“1x+0y-3”
d=“0x+1y-0.5”
result=[float(s) for s in re.findall(r’-?\d+.?\d*’,a)]
result1=[float(s) for s in re.findall(r’-?\d+.?\d*’,b)]
result2=[float(s) for s in re.findall(r’-?\d+.?\d*’,c)]
result3=[float(s) for s in re.findall(r’-?\d+.?\d*’,d)]
print(result)
print(result1)
print(result2)
print(result3)
0, 1.0, 0.0]
[1.0, -1.0, 0.0]
[1.0, 0.0, -3.0]
[0.0, 1.0, -0.5]

Sure.

Though the equation for “line” C makes no sense; If you rearrange it into a slope-intercept form, you end up with 0y = 1x - 3. You can’t divide by 0; so this becomes 0 = 1x - 3, or x = 3, but this ‘line’ is false at all values of x except for when X is 3.

Nothing can be above or below a vertical line. So you’ll need a different metric for measuring separation.

I think what they’re trying to get you to do is apply the distance metric…

Slightly more complex, but… fine.

(Minimum) Distance from a point on a line is given as: But you want to remove the absolute value from the numerator, because you care about whether it’s on one side of the line or the other.

In this situation, b being 0 is trivial, as long as a is not also 0. (if a and b are both 0, you have a definition that does not draw a line.)

Hi I would like to know the logic for this question. As I have to work on my assignment. Tq in advance!