1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
| #include <bits/stdc++.h> #define LL long long
using namespace std;
const int Maxn = 1e6 + 10; const double inf = DBL_MAX, eps = 1e-14;
int N, L; struct node { int d, v, w, id; double dis; }A[Maxn], p[Maxn], tmp[Maxn];
inline int cmp (node a, node b) { return a.d < b.d; }
int Max, last, Vis[Maxn];
inline void Solve (int l, int r) { if (l >= r) return ; int mid = (l + r) >> 1; Solve (l, mid); Solve (mid + 1, r); int p1 = l, p2 = mid + 1, p3 = l; double L1 = inf, L2 = inf, R1 = -inf, R2 = -inf; double TL1 = inf, TL2 = inf, TR1 = -inf, TR2 = -inf; while (p1 <= mid || p2 <= r) { if (p2 > r || (p1 <= mid && p[p1].w > p[p2].w)) { if (p3 > l && tmp[p3 - 1].w > p[p1].w) L1 = TL1, R1 = TR1, L2 = TL2, R2 = TR2; if (L2 <= p[p1].dis || R2 - L >= p[p1].dis) Vis[p[p1].id] = 1; TL1 = min(TL1, p[p1].dis); TR1 = max(TR1, p[p1].dis); tmp[p3++] = p[p1++]; } else { if (p3 > l && tmp[p3 - 1].w > p[p2].w) L1 = TL1, R1 = TR1, L2 = TL2, R2 = TR2; if (L1 + L <= p[p2].dis || R1 >= p[p2].dis) Vis[p[p2].id] = 1; TL2 = min(TL2, p[p2].dis); TR2 = max(TR2, p[p2].dis); tmp[p3++] = p[p2++]; } } for (int i = l; i <= r; ++i) p[i] = tmp[i]; }
inline int Check (double x) { for (int i = 1; i <= N; ++i) { p[i] = A[i], Vis[i] = 0; p[i].dis = p[i].d + x * p[i].v; } Solve (1, N); for (int i = 1; i <= N; ++i) if (!Vis[i] && A[i].w != Max) { last = i; return 0; } return 1; }
inline void update (node a, node b, int &ans1, int &ans2) { if (a.v < b.v) swap(a, b); LL x = a.v - b.v, y; if (a.d < b.d) y = b.d - a.d; else y = L - a.d + b.d; if (y * ans1 <= x * ans2) ans1 = x, ans2 = y; }
int main() { #ifdef hk_cnyali freopen("A.in", "r", stdin); freopen("A.out", "w", stdout); #endif int T; scanf("%d", &T);
while (T--) { scanf("%d%d", &N, &L); for (int i = 1; i <= N; ++i) scanf("%d", &A[i].d); for (int i = 1; i <= N; ++i) scanf("%d", &A[i].v); for (int i = 1; i <= N; ++i) scanf("%d", &A[i].w); sort(A + 1, A + N + 1, cmp); for (int i = 1; i <= N; ++i) A[i].id = i;
Max = 0; for (int i = 1; i<= N; ++i) Max = max(Max, A[i].w);
double l = 0, r = L; last = 0;
while (l + eps < r) { double mid = (l + r) / 2; if (Check (mid)) r = mid; else l = mid; } if (!last) { cout<<0<<endl; return 0; } int ans1 = 0, ans2 = 0; for (int i = 1; i <= N; ++i) if (A[i].w > A[last].w) update(A[i], A[last], ans1, ans2); cout<<ans2 / __gcd(ans1, ans2)<<"/"<<ans1 / __gcd(ans1, ans2)<<endl; } return 0; }
|