All Tracks Algorithms Searching Binary Search Problem

Perfect Alignment
Tag(s):

Algorithms, Binary Search, Easy-Medium, Greedy, Searching, Two-pointer

Problem
Editorial
Analytics

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).

Note:

  • 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\)

 

SAMPLE INPUT
4
1
1 5
1
1 7
1
1 9
1
1 359
SAMPLE OUTPUT
12
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?