You are not logged in. Please login at www.codechef.com to post your questions!

×

Codeforces Problem Anton and Lines

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

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%


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

image

link

answered 05 Nov '15, 18:51

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

(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★

Hmmm... Interesting

link

answered 05 Nov '15, 20:45

pawelmusan's gravatar image

0★pawelmusan
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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