×

# Codeforces Problem Anton and Lines

 1 Let's say I have n pairs of integers (not necessarily positive. The ith line consists of a pair of numbers ai and bi. What is the quickest way to find if (bj - bi) / (ai - aj) lies within a certain range? I can only think of the usual O(N^2) solution but a solution of lesser time complexity? I am trying to solve Anton and Lines from Round 329 on Codeforces. Problem link: http://codeforces.com/contest/593/problem/B asked 05 Nov '15, 17:30 2★sandy999 391●1●16●38 accept rate: 10%

 2 NOTE : I found this on a codeforces blog and I thought it would help you. It was written by DollarAkshay so all credits goes to him. If you try a brute force method of checking each pair you wont pass because its a O(n^2) algorithm. Instead of lines think of them as line segments from X1 to X2 You have to find the y intercepts at X1 and X2. Create a pair vector of the form { line_number , X1_Y_intercept} Create another pair vector of the form { line_number , X2_Y_intercept} Sort them both based on X1_Y_intercept and X2_Y_intercept." Now if the ordering of the line_number is the same in both vectors then there is no intersection else there is an intersection answered 05 Nov '15, 18:51 4★bhishma 297●7 accept rate: 11% Here is my ACed solution in java http://codeforces.com/contest/593/submission/14078868 (05 Nov '15, 18:54) bhishma4★ Ahhh, I never thought of them geometrically as line segments, merely solutions of the line equations. Thanks! btw, regarding my first question, is there no way out? (05 Nov '15, 19:32) sandy9992★ Sorry I can't understand your problem , can you be more precise. (05 Nov '15, 19:38) bhishma4★
 0 Hmmm... Interesting answered 05 Nov '15, 20:45 1 accept rate: 0%
 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:

×686

question asked: 05 Nov '15, 17:30

question was seen: 2,086 times

last updated: 05 Nov '15, 20:45