CF924D Contact ATC
思路：考虑函数 \(\operatorname{F}(v_0)_i\) 表示风速为 \(v_0\) 时，\(i\) 到达原点的时间，易得：
\[\operatorname{F}(v_0)_i = \frac{x_i}{v_i+v_0}\]
则若 \((i,j)\) 满足条件，需要满足 \(\operatorname{F}(v_0)_i\) 与 \(\operatorname{F}(v_0)_j\) 的交点的横坐标在 \([-m,m]\) 间，那么若 \(\operatorname{F}(v_0)_i=\operatorname{F}(v_0)_j\)，即 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\)。
根据零点存在定理：若区间 \(\) 满足 \(\operatorname{f}(l) \le 0\) 且 \(\operatorname{f}(r) \ge 0\)，且函数连续，则 \(\) 至少有一个 \(\operatorname{f}(x)\) 的零点。
那么判定 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\) 在 \([-w,w]\) 是否有零点，只需要满足 \(\operatorname{F}(-w)_i-\operatorname{F}(-w)_j \le 0\) 且 \(\operatorname{F}(w)_i-\operatorname{F}(w)_j \ge 0\)
注意到 \(\operatorname{F}(x)_i\) 有单调性，则设 \(l_i=\operatorname{F}(-w)_i,r_i=\operatorname{F}(w)_i\)。
则需要满足 \(l_i \le l_j=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double ld;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=1e6+10;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c
页:
[1]