Repository contains computational geometry problem that was a candidate for Infobip Coding Challenge in January 2021.
Given n rotating line segments of length 1m in a plane and the following constraints:
- Each line segment kicks off its rotation from a vertical position and rotates around its lower endpoint.
- Each line segments makes a full circle in 2pi seconds.
your goal is to find the sorted list of time intervals in radians (within a [0, 2pi] period) in which any of the segments is within the rotation circle of any other line segment.
Each segment is given as a pair of coordinates of its lower endpoint (rotation center).
Sample input:
0.5 0
-0.5 0
Sample output:
0.52358 2.618
3.66518 5.75959
Precision: 1e-5
Expected runtime complexity: O(nlog(n + k)
, where k is the number of intersections of rotation circles.
To generate new test case:
python3 tests/test_generator.py <test_case_size>
To benchmark the algorithms:
pypy rotors.py <input_test_case_path> <output_test_case_path> <method>
Available method
args:
all
: Runs all implemented algorithmsquadratic
: Runs a O(n^2) solutionexpected_nlogn
: Runs a expected O(nlogn) solution (worst case O(n^2))nlogn
: Runs worst case nlog(n + k) solution, where k is the number of intersections. (NOT DONE YET!)