×

# RED BLUE using Binary Search

 5 My solution was similar but didn't involve much thinking: Choose a point as centre. Then sort the rest of the points according to slope with the respect to the centre. Now join centre to any other point and radially sweep this line to count how many points of each color are there on either side of line. Same complexity since we choose centre $n$ times and $O(n\log n + n)$ for sorting and radial sweep. answered 11 Dec '17, 16:46 6★gear4 106●3 accept rate: 0% This is also my solution (as a tester for this contest). The author's solution is a bit more complicated, but has the same time complexity. (12 Dec '17, 13:34)
 2 A very elegant solution indeed! answered 11 Dec '17, 18:29 5★arunava5 51●1 accept rate: 0% 1 thanx dada:) (11 Dec '17, 18:38)
 2 Too nice to be a solution! Awesome editorial. answered 11 Dec '17, 22:16 51●4 accept rate: 0%
 2 Very nice editorial, I was trying something like this method but I couldn't implement it answered 11 Dec '17, 23:04 3★mohit122 21●2 accept rate: 0%
 1 That was just awesome. It'll Be great if you make a video editorial for it. Some things are bit confusing like "extending slope to all quadrants". answered 11 Dec '17, 23:22 4★vaibzz 100●5 accept rate: 12% 1 extending to all quadrants means same thing can be done for all quadrants. Example for quadrant 2 , if you have a line with slope P ,then you can see all lines that come above it have slope lesser than it in 2nd quad as there slopes are -ve. 3rd quad is similar to frst and 4th to 2nd. Just try drawing on a paper. :) Btw i will try making video editorials too :) (11 Dec '17, 23:26) yeah! I got your point. Thanks. Good luck for videos. I'll be the first to watch :P (12 Dec '17, 01:16) vaibzz4★
 0 Awesome thinking and implementation indeed!! answered 12 Dec '17, 12:52 4★monsij 73●5 accept rate: 0% thank you :) (12 Dec '17, 15:06)
 0 I couldn't solve this question, i didn't know where to start from, can you explain why the naive solution works? I'm unable to crack it. answered 13 Dec '17, 12:22 1●1 accept rate: 0% See what I am doing is taking a red and blue point joining a line between them and assuming that our solution line is not exactly this(solution line can't pass through points) but it lies very close to this line with both points lying on opposite side. So two cases will be there with blue and red points in opposite direction. Now we need to find how many points to be deleted i.e. how many red points will be on opposite side of the chosen side of red points and how many blue pts on other side. Do this for both cases (13 Dec '17, 19:47)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×163
×63
×31

question asked: 11 Dec '17, 16:31

question was seen: 6,042 times

last updated: 19 Feb, 11:10