algorithm for finding a straight line to separate class
First sort data base on their $y$ value. Then find the minimum and maximum value between members of the second class which is denoted by $y_{min_2}$ and $y_{max_2}$, respectively. Then, line with equation of $y = y_{min_2}$ and $y = y_{max_2}$ are candidate. We can count the number of first class member in sides of these two lines in $O(\log(n))$.

Therefore, we find an algorithm which works in $O(n\log(n))$.