[NCD 2019] G. Ali and the Breakfast (解析几何)

G. Ali and the Breakfast

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Ali Mansour was having a breakfast with his friends at the dorm. He will pour tea in their cups. He wanted to make the breakfast more exciting, so he decided to throw a drop of tea at their cups.

Ali will throw the drop randomly from point (0,0)(0,0) at a random (formally random) angle between LL and RR with initial speed VV.

He has NN friends, and each has a cup of different width. Let's assume that each cup has a 00 height and is placed on the ground (The XX Axis). Given each cup's position, for each cup calculate the probability that the drop will fall in this cup. Note: it's possible for two cups to overlap or intersect.

Input

First line of input will be TT the number of test cases.

Each test case is described by 44 space separated integers, N,V,L,RN,V,L,R (1≤N≤10001≤N≤1000), (1≤V≤1091≤V≤109), (0≤L≤R≤900≤L≤R≤90).

Then NN lines, the positions of the cups (X1iX1i, X2iX2i), (0≤X1i<X2i≤1090≤X1i<X2i≤109)

Output

For each test case print NN lines. in the IthIth line print the probability that the drop will fall in the IthIth cup.

Print the probability rounded to exactly 44 digits

Example

input

Copy

1
5 15 30 45
16 21
21 22
22 30
10 15
1 40

output

Copy

0.2987
0.2979
0.4034
0.0000
1.0000

Note

Consider gg = 1010 mm.s−2

题意:

\(\mathit T\)组数据,每一组数组给定以下信息:

随机角度\(\theta\)的范围\([L,R]\),平抛运动的初速度\(v_0\),以及\(\mathit n\)个询问。

每一个询问给定两个整数\(x_1,x_2\),代表\(X\)轴上一段连续的区域。

你需要回答在角度\(\theta\)在范围\([L,R]\)等概率选择一个数值时,平抛运动落在\(\mathit X\)轴这段区域的概率是多少?

思路:

根据平抛运动的对称性进行物理学分析得知平抛运动如果落在位置\(\mathit S\)时的角度满足:

\(sin(2\theta)=\frac{S*g}{v_0^2}\)

我们将\(x_1,x_2\)分别代入上式得到对应的\(\theta\),然后与角度范围\([L,R]\)做比即可。

但是本题需要注意以下三点:

  • \(x_1,x_2\)的范围较大,double 型变量无法达到准确的精度,故需要使用 long double,想使用返回long double 的系统函数,所有函数后面要加一个l

  • 如果给定的区间\([L,R]\)是一个点,即\(L=R\),只需要特判以下角度\(\mathit L\)是否满足条件,如果满足答案是1,否则是0,如果不判断,\(R-L=0\),会导致除以0的情况,这是不合法的运算。

  • \(2\theta\),可能为\([0,\frac{\pi}{2}],[\frac{\pi}{2},\pi]\)这2种区间取值,而C++的反正弦函数\(asin\)只返回在\([0,\frac{\pi}{2}]\)的区间的。如下图:

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const long double pi = acosl(-1);
long double getceta(long double s, long double v0, long double limit)
{
    long double res;
    s *= 10;
    s /= v0 * v0;;
    if (s > 1)
        return limit;
    res = asinl(s);
    res /= 2;
    return res;
}
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    int t;
    t = readint();
    while (t--)
    {
        int n = readint();
        int v = readint();
        long double l = readint();
        long double r = readint();
        long double M = ( long double)v * v / 10;
        l = l * pi / 180;
        r = r * pi / 180;
        repd(i, 1, n)
        {
            long double sx = readint();
            long double ex = readint();
            ex = min(ex, M);
            if (sx - eps > ex)
            {
                puts("0.0000");
                continue;
            }
            long double sceta = getceta(sx, v, l);
            long double eceta = getceta(ex, v, r);
            sceta = fabsl(sceta);
            eceta = fabsl(eceta);
            long double ans = max((long double)0.00, (min(eceta, 1.0 * r) - max(sceta, 1.0 * l)) / (r - l));
            ans += max((long double)0.0, (min((pi - sceta * 2) / 2, r) - max((pi - eceta * 2) / 2, l)) / (r - l));
            ans = max(ans, (long double)0.000);
            ans = min(ans, (long double)1.0);
            if (r - l < 1e-12) {
                long double X = ( long double)v * v / 10 * sinl(2 * l);
                if (X > sx - 1e-8 && X < ex + 1e-8) {
                    puts("1.0000");
                } else {
                    puts("0.0000");
                }
            } else {
                cout.setf(ios::fixed);
                long double X = ( long double)v * v / 10 * sinl(2 * l);
                cout << setprecision(4) << X << endl;
                X = ( long double)v * v / 10 * sinl(2 * r);
                cout << setprecision(4) << X << endl;
                cout << setprecision(4) << ans << endl;
            }
        }
    }

    return 0;
}