Timeline for Find the longest uninterrupted arc
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2020 at 7:48 | comment | added | Quelklef | Here is my degolf + 3:30AM writeup of this answer, if anyone else is interested in how it works. | |
| Aug 18, 2020 at 7:44 | comment | added | Quelklef | @Anush I degolfed it and, after probably hours of investigation, have concluded that it's legit. It seems to work as follows. It splits the circle into n equal segments, where n is the number of points. In each segment, it records the min and max angle. The longest arc is then found by comparing the max angle of one segment to the min angle of the next nonempty segment. This utilizes the fact that the longest arc will always span multiple segments since it must always be at least 2pi/n radians in length. Very very clever solution! I hope OP doesn't mind me revealing their secrets ;P | |
| Jul 24, 2020 at 8:19 | comment | added | user9207 | Unless the points are always given in order around the circle, an O(n) time solution is not possible. | |
| Jun 27, 2018 at 20:49 | vote | accept | F Chopin | ||
| May 14, 2018 at 21:46 | comment | added | F Chopin | I still don't understand how this works, but I am willing to accept this as the answer once I have the chance to run extensive test cases. Even though it is longer than the other answer, it has a lower time complexity. | |
| May 14, 2018 at 13:10 | comment | added | l4m2 | but in this case is array manuing still O(1)? | |
| May 14, 2018 at 13:07 | comment | added | l4m2 | How stupid I was | |
| May 14, 2018 at 13:07 | history | edited | l4m2 | CC BY-SA 4.0 |
deleted 16 characters in body
|
| May 14, 2018 at 3:33 | history | edited | l4m2 | CC BY-SA 4.0 |
added 1 character in body
|
| May 13, 2018 at 16:35 | history | edited | l4m2 | CC BY-SA 4.0 |
added 384 characters in body
|
| May 13, 2018 at 16:21 | history | edited | l4m2 | CC BY-SA 4.0 |
added 96 characters in body
|
| May 13, 2018 at 16:17 | history | answered | l4m2 | CC BY-SA 4.0 |