ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1103. Pencils and Circles

My algo complexity is O(n^4), Is it exists any more efficient? (-)
Posted by Victor Barinov (TNU) 11 May 2005 18:09
Re: My algo complexity is O(n^4), Is it exists any more efficient? (-)
Posted by Burunduk1 11 May 2005 20:25
Algo which I wrote is O(n*logn) but also I know O(n) one.

Try to choose one point which will be on the circle. O(1)
Than try to choose another one point which will be on the circle. O(n*logn) or O(n)
Finally build circle by these two points. O(n)

PS: I used such two points that all other points are at one side of the line which contains these two points.
Why!?
Posted by Victor Barinov (TNU) 12 May 2005 00:04
I not understand why your algo is right. Maybe we'll discuss some questions by e-mail. Mine is victorbarinov@ua.fm
Thanks!
Re: Why!?
Posted by Ripatti [Ufa] 23 Nov 2010 16:45
My simple linear solution uses Inversive geometry.

1. Inverse plane with respect to one of points (let it is A). O(n).
2. Chose another (not A) most left point (let it is B). O(n).
3. Sort all points without A and B with respect to B by polar angle and chose middle (let it is C). We want to get exactly one element on middle place, so I used std::nth_element which work O(n).
4. Output A, B, C. O(1).
Re: Why!?
Posted by KNIGHT0X300 10 Feb 2013 15:44
I can guarantee that the above algorithm is working. I came up with a similar algorithm :)
Re: Why!?
Posted by c_pp 9 Jan 2017 20:55
Thx @Ripatti [Ufa].
A solve with O(n) , got AC 0.001s.

Hint for others:
1. did not need any math functions, like  acos, atan.  use simple vector multiplications.
2. calc cos(v[i]) , i>2.  values before sorting.
3. use std::nth_element
4. if need more speed, use buffered i/o.

Good Luck!!