All Tracks Algorithms Searching Binary Search Problem

Perfect Alignment

Algorithms, Binary search algorithm, Easy-Medium, Greedy algorithm, Searching algorithm, Two pointer


You are given a pile of \(n\) identical disks stacked on top of each other with their centers aligned vertically. Each disk has a hole at a certain radius from the center. A disk can have multiple holes on it but no two holes are at the same distance from the center. You can rotate the disks in either clockwise or anticlockwise direction but the cost to rotate it by \(d\) degrees is \(d\)  (\(d\) can be any positive real number). Each disk can be rotated independently of each other. Determine the minimum cost to rotate the disks in such a way that at least one of the holes is aligned from the top to the bottom of the pile of disks (that is, all the holes should be at the same radial angle).


  • An aligned hole means you can look from the top disk all the way down through the bottom disk through the hole. 
  • Consider the disks to be centered at the origin and the radial angle of holes given as the angle from \(+x\)  axis in the anticlockwise direction (from \(0\) degrees to \(360\) degrees).
  • Assume that all the disks have a very large radius and the holes have negligible radius.

Input format

  • First line: \(n\) (the number of disks)
  • \(i^{th}\) disk is decribed as:
    • First line: \(h_i\) (the number of holes in the \(i^{th}\)disk)
    • Next \(h_i\) lines: Two space-separated numbers \(r_i\) (the radial distance of the hole) and  \(d_i\) (the radial angle of the hole up to \(6\) decimal places)

Output format

Print the minimum cost to align one of the holes from the top disk to the bottom disk of the pile. If it is not possible to align any hole, print \(-1\). If the absolute difference between the output and the correct answer is \(\le10^{-6}\), the output will be considered correct.

Input Constraints

\(1\le n \le 200000\)

\(0<r_i\le 10^9\)

\(0.0\le d_i<360.0\)

\(0\le\sum\limits_{i=1}^n \ h_i\le10^6\)


1 5
1 7
1 9
1 359

All the holes are at same radius.The cost to align all holes is minimum if all the holes are aligned at 5 degrees (by rotating disks 2 and 3 in clockwise direction by 2 and 4 degrees respectively and disk 4 in anticlockwise direction by 6 degrees).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications