ToB企服应用市场:ToB评测及商务社交产业平台

标题: CF924D Contact ATC [打印本页]

作者: 花瓣小跑 时间: 2024-8-22 12:38
标题: 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\)。
根据零点存在定理：若区间 \([l,r]\) 满足 \(\operatorname{f}(l) \le 0\) 且 \(\operatorname{f}(r) \ge 0\)，且函数连续，则 \([l,r]\) 至少有一个 \(\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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)