This page is still under construction.

Parts of this page are still being built. What you see may change.

Jogging

Time limit1sMemory limit16 MB

Summary
For each rest point given in increasing order, print the largest angle in radians to a star with greater x, or zero when no such star exists.
Level

Medium7 of 10

Topics
Geometry, Sorting, Two pointers
Solved
No attempts yet

Problem

Daeyoung lives in a two dimensional world, so he is a single point on the xx axis. He jogs every evening and runs only in the direction of increasing xx. In this world the sky fills with stars as soon as evening comes. When the running tires him out, Daeyoung stops for a while and looks up at the stars.

A star is also a point in the plane. Daeyoung looks only at the stars whose xx coordinate is greater than his own, and he wants to know which of them is the highest. Highest means the star that makes him raise his head the most, that is, the star with the largest angle.

If Daeyoung rests at the point (p,0)(p, 0) and a star is at the point (x,y)(x, y), the angle to that star is the angle θ=arctan⁡yx−p\theta = \arctan \frac{y}{x - p} between the positive direction of the xx axis and the ray toward the star. For every rest, find the largest angle among the stars visible at that moment.

The angle between jogging Daeyoung and a star

Input

The first line contains the number of stars NN and the number of rests MM, separated by a space. (1≤N≤1051 \le N \le 10^5, 1≤M≤1051 \le M \le 10^5)

Each of the next NN lines contains two integers xx, yy separated by a space, the coordinates of one star. (∣x∣≤108|x| \le 10^8, 1≤y≤1081 \le y \le 10^8)

Each of the next MM lines contains the xx coordinate where Daeyoung rests, one per line. These coordinates are given in increasing order and their absolute value is at most 10810^8.

Several stars can share the same xx coordinate.

Output

For each rest, print the largest angle among the visible stars in radians, rounded to seven digits after the decimal point, one per line. Print 0.0000000 when no star is visible.

The judge compares the printed text exactly. In every test the answer is far enough from a rounding boundary that double precision arithmetic produces the same text.

Examples3

  1. Example 1

    Input
    2 3
    4 4
    6 6
    -1
    1
    4
    
    Expected output
    0.7086263
    0.9272952
    1.2490458
    
  2. Example 2

    Input
    1 1
    5 5
    0
    
    Expected output
    0.7853982
    
  3. Example 3

    Input
    3 4
    -5 3
    0 7
    5 2
    -6
    -5
    0
    5
    
    Expected output
    1.2490458
    0.9505468
    0.3805064
    0.0000000