题解 P6214 【「SWTR-04」Taking a Walk】
xtx1092515503 · · 题解
应出题人要求，前来研究本题，然后发现出题人的写法一点也不美观。
我们考虑任意时刻两人之间的向量
考虑两人间的距离，它为
明显，点到直线距离是二次函数（考虑点到直线距离公式）。这就意味着，我们如果把每一时刻二人间距离画出来，它可能长这样：
如图，距离可能曲里拐弯，可能上下乱动，但是唯一不变的是，在每个区间内，距离要么是单调上升/下降的，要么是单峰的。
于是，我们可以再把每个单峰函数在峰值处切一刀，将其切成两半单调的函数。
于是现在，我们便得到了众多单调的连续函数。
我们现在再考虑询问距离为
明显，依据中值定理，对于一段函数
于是我们便可以离线下所有询问，然后从小到大依次枚举每一段
具体而言，我们可以将询问按照键值排序，关于询问建线段树，然后在线段树上维护区间
说起来很轻巧，但是写起代码来却异常恶心。
首先，初始的函数可以通过对两个人进行归并得到。这时，我们便知道了每一段函数的分界点、函数在分界点处的取值，以及每段区间内部的速度（即上述的
然后，关于将二次函数切开的操作，可以使用三分——但我认为那是异端行为。更好的方法是采用计算几何求出原点到上述直线的垂线，然后在垂足处将二次函数分开。
然后建树什么的就不提了。注意，区间的端点要单独考虑，不然会出现奇怪的错误（因为端点会被左右两端的区间各计算一次）。
然后就是求询问与某段函数的交点了。可以使用二分——但那还是异端行为。更好的方法是直接上计算几何，计算出当直线上的某个点离原点的距离是询问的值时，其与垂足间的距离（可以直接上勾股定理算得），然后判断垂足两端距离它为上述距离的点中哪一个在区间内即可。
最后是两种特殊情况：
时间复杂度
（所以，为什么还要用主席树呢？）
（虽然此代码一点都不比主席树短）
代码：
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
struct Vector{
double x,y;
Vector(){x=y=0;}
Vector(double X,double Y){x=X,y=Y;}
friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
friend Vector operator /(const Vector &u,const double &v){return Vector(u.x/v,u.y/v);}
friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
friend double operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}//point times
double operator ~()const{return sqrt(x*x+y*y);}//the modulo of a vector
double operator !()const{return atan2(y,x);}//the angle of a vector
void read(){scanf("%lf%lf",&x,&y);}
void print(){printf("(%lf,%lf)",x,y);}
};
typedef Vector Point;
struct Line{
Point x,y;
Vector z;
Line(){}
Line(Point X,Point Y){x=X,y=Y,z=Y-X;}
friend Point operator &(const Line &u,const Line &v){return u.x+u.z*((v.z&(u.x-v.x))/(u.z&v.z));}
};
typedef Line Segment;
namespace ini{//initialization part.
int n,m,lim;
Vector A[80100],B[80100],v[160100];
double aa[80100],bb[80100],tim[160100];
Point p[160100],tange[160100];
double FindTangent(int i){
if(~v[i+1]<eps||~p[i]<eps){tange[i]=p[i];return 0;}
Line U=Line(p[i],p[i]+v[i+1]);
Line V=Line(Point(),Point(v[i+1].y,-v[i+1].x));
Point W=U&V;
tange[i+1]=W;
W=W-p[i];
if((W|v[i+1])<0)return 0;//the inflection point is <0.
return ~W/~v[i+1];
}
}
namespace nin{//function part.
int q,lim;
Vector v[320100];
double tim[320100];
Point p[320100],tange[320100];
double FindConcide(int i,double req){
double mini=~tange[i+1];
double nedi=sqrt(req*req-mini*mini)/~v[i+1];
Point W=tange[i+1]-p[i];
double nowi=~W/~v[i+1];
if((W|v[i+1])<0)nowi=-nowi;
if(nowi+nedi>eps&&nowi+nedi<=tim[i+1]-tim[i])return nowi+nedi+tim[i];
return nowi-nedi+tim[i];
}
struct Query{
int num,id;
double inq;
friend bool operator <(const Query &x,const Query &y){return x.inq<y.inq;}
}qq[301000];
double qwq[301000];
double res[301000];
set<double>sp;
bool findsp(double inq){
auto it=sp.lower_bound(inq);
if(it!=sp.end()&&fabs(*it-inq)<eps)return true;
if(it==sp.begin())return false;
it--;
return fabs(*it-inq)<eps;
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct Segtree{
int tag,mn;
}seg[1201000];
void ADD(int x,int y=1){seg[x].tag+=y,seg[x].mn-=y;}
void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);}
void build(int x,int l,int r){
if(l==r){
if(findsp(qq[l].inq))res[qq[l].id]=-2.33,seg[x].mn=0x3f3f3f3f;
else seg[x].mn=qq[l].num;
return;
}
build(lson,l,mid),build(rson,mid+1,r),pushup(x);
}
void modify(int x,int l,int r,int L,int R){
if(l>R||r<L)return;
if(L<=l&&r<=R){ADD(x);return;}
pushdown(x),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R),pushup(x);
}
void getans(int x,int l,int r,int i){
if(l==r){
res[qq[l].id]=FindConcide(i,qq[l].inq);
seg[x].mn=0x3f3f3f3f;
return;
}
pushdown(x);
if(seg[lson].mn==0)getans(lson,l,mid,i);
if(seg[rson].mn==0)getans(rson,mid+1,r,i);
pushup(x);
}
void setans(int x,int l,int r,double i){
if(l==r){
res[qq[l].id]=i;
seg[x].mn=0x3f3f3f3f;
return;
}
pushdown(x);
if(seg[lson].mn==0)setans(lson,l,mid,i);
if(seg[rson].mn==0)setans(rson,mid+1,r,i);
pushup(x);
}
}
namespace ini{
void initialize(){
scanf("%d%d%d",&n,&m,&nin::q);
A[0].read(),B[0].read();
for(int i=1;i<=n;i++)A[i].read(),scanf("%lf",&aa[i]);
for(int i=n;i;i--)A[i]=(A[i]-A[i-1])/(aa[i]-aa[i-1]);
for(int i=1;i<=m;i++)B[i].read(),scanf("%lf",&bb[i]);
for(int i=m;i;i--)B[i]=(B[i]-B[i-1])/(bb[i]-bb[i-1]);
for(int i=1,j=1;i<=n&&j<=m;){
tim[++lim]=min(aa[i],bb[j]);
v[lim]=A[i]-B[j];
if(fabs(aa[i]-tim[lim])<eps)i++;
if(fabs(bb[j]-tim[lim])<eps)j++;
}
p[0]=A[0]-B[0];
for(int i=1;i<=lim;i++)p[i]=p[i-1]+v[i]*(tim[i]-tim[i-1]);
}
}
namespace nin{
void solution(){
// p[0].print(),puts("");for(int i=1;i<=lim;i++)v[i].print(),printf("%lf\n",tim[i]),p[i].print(),puts("");
for(int i=0;i<lim;i++)if(~v[i+1]<eps)sp.insert(~p[i]);
for(int i=1;i<=q;i++)scanf("%lf%d",&qq[i].inq,&qq[i].num),qq[i].id=i;
sort(qq+1,qq+q+1);
// for(int i=1;i<=q;i++)printf("%lf %d %d\n",qq[i].inq,qq[i].num,qq[i].id);
for(int i=1;i<=q;i++)qwq[i]=qq[i].inq;
build(1,1,q);
for(int i=0;i<lim;i++){
if(~v[i+1]<eps)continue;
double l=~p[i],r=~p[i+1];
if(l>r)swap(l,r);
l+=eps,r-=eps;
// printf("%lf %lf\n",l,r);
int L=upper_bound(qwq+1,qwq+q+1,l)-qwq;
int R=upper_bound(qwq+1,qwq+q+1,r)-qwq-1;
// printf("%d %d\n",L,R);
if(L<=R)modify(1,1,q,L,R);
// printf("BEF:%d\n",seg[1].mn);
if(seg[1].mn==0)getans(1,1,q,i);
// printf("AFT:%d\n",seg[1].mn);
double w=~p[i+1];
L=lower_bound(qwq+1,qwq+q+1,w)-qwq;
R=upper_bound(qwq+1,qwq+q+1,w)-qwq-1;
if(L<=R)modify(1,1,q,L,R),printf("%d %d\n",L,R);
if(seg[1].mn==0)setans(1,1,q,tim[i+1]);
}
for(int i=1;i<=q;i++)if(fabs(res[i])<eps)res[i]=-4.66;
for(int i=1;i<=q;i++)printf("%.9lf\n",res[i]);
}
}
int main(){
ini::initialize();
nin::p[0]=ini::p[0];
for(int i=0;i<ini::lim;i++){
double pos=ini::FindTangent(i);
if(pos>eps&&(ini::tim[i+1]-ini::tim[i])-pos>eps){
nin::lim++;
nin::p[nin::lim]=ini::p[i]+ini::v[i+1]*pos;
nin::v[nin::lim]=ini::v[i+1];
nin::tim[nin::lim]=ini::tim[i]+pos;
nin::tange[nin::lim]=ini::tange[i+1];
}
nin::lim++;
nin::p[nin::lim]=ini::p[i+1];
nin::v[nin::lim]=ini::v[i+1];
nin::tim[nin::lim]=ini::tim[i+1];
nin::tange[nin::lim]=ini::tange[i+1];
}
nin::solution();
return 0;
}