P28755 [洛谷] [SHOI2014] Signal Amplifier
提高+
题目描述

Problem Description

In an ideal scenario, the effective signal coverage area of a wireless network base station is a circle. The power consumption of the base station is proportional to the square of the circle's radius. Given the positions of several network users on a plane, you are tasked with selecting an appropriate location to build a wireless base station...

Just as you are about to start coding, your inventor friend SHTSC suddenly appears. SHTSC has just completed his new invention—the wireless signal amplifier. This amplifier can extend the effective signal coverage range in a specific direction without increasing the base station's power consumption. That is, the coverage area of a base station equipped with an amplifier is an ellipse, and its power consumption is proportional to the square of the length of the semi-minor axis.

Given the positions of several network users on a plane, you need to choose a suitable location to build a wireless base station and, with the help of the amplifier, ensure that all users can receive the signal while minimizing the base station's power consumption.

Note: Due to the working principle of SHTSC's amplifier, which relies on the Earth's magnetic field, the amplification direction is fixed.

Input Format

The first line contains an integer: n. The number of users on the plane. The next n lines each contain two integers x, y, representing the position of a user.

The n+2nd line contains an integer: a. This indicates the amplification direction of the amplifier in degrees. It means the direction of the amplifier is rotated a degrees counterclockwise from the positive x-axis.

The n+3rd line contains an integer: p. This indicates the amplification factor of the amplifier.

Output Format

Output a single line containing a real number, which is the length of the semi-minor axis of the smallest ellipse that can cover all users, rounded to three decimal places.

Sample Input and Output

Sample Input #1

2
1 0
-1 0
0
2

Sample Output #1

0.500

Sample Input #2

3
1 1
-1 -1
0 0
45
7

Sample Output #2

0.202

Notes

  • For 10% of the data, the optimal solution's center is guaranteed to be at the origin.
  • For 20% of the data, the points are guaranteed to be randomly generated.
  • For 30% of the data, n ≤ 100.
  • For 50% of the data, n ≤ 5000.
  • For 100% of the data, n ≤ 50000, 0 ≤ a < 180, 1 ≤ p ≤ 100, |x|, |y| ≤ 2 × 10^8.
输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
2 1 0 -1 0 0 2
样例输出
0.500