bzoj3570 Dzy Loves Physics I
ShinriiTin
posted @ 2015年6月11日 18:28
in 未分类
with tags
不知道这是个什么玩意儿系列
, 472 阅读
看到题面就傻了。。。
完全弹性碰撞:m1v1+m2v2=m1v1'+m2v2'
由动能定理得:0.5*m1*v12+0.5*m2*v2=0.5*m1*v1'2+0.5*m2*v2'2
当m1=m2时,v1'=v2,v2'=v1
又有条件a*v=C,即dv/dt *v=C
两边同时积分得: 0.5*v2=C*t
解得v=sqrt(2*C*t)
所以。。。求原来k小的速度,再算出现在的速度即可
#include <math.h> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MAXN=1e5+5; int bit[MAXN],sz; inline void Add(int x){ for(;x<=sz;x+=x&-x)++bit[x]; } inline int kth(int k){ int ans=0; for(int i=19;~i;--i){ ans+=1<<i; if(ans>=sz||bit[ans]>=k)ans-=1<<i; else k-=bit[ans]; } return ans+1; } int n,q,C,a[MAXN],h[MAXN<<1]; int opt[MAXN],t[MAXN],x[MAXN]; inline int Hash(int x){ return lower_bound(h+1,h+1+sz,x)-h; } int main(){ scanf("%d%d",&n,&C); for(int i=1;i<=n;++i){ scanf("%d%*d%*d",a+i); h[++sz]=a[i]; } scanf("%d",&q); for(int i=1;i<=q;++i){ scanf("%d",opt+i); if(opt[i])scanf("%d%d",t+i,x+i); else scanf("%d%*d%*d",x+i),h[++sz]=x[i]; } sort(h+1,h+1+sz); sz=unique(h+1,h+1+sz)-(h+1); for(int i=1;i<=n;++i)Add(Hash(a[i])); for(int i=1;i<=q;++i){ if(opt[i]){ int v=h[kth(x[i])]; printf("%.3f\n",sqrt(2.*C*t[i]+1.*v*v)); } else Add(Hash(x[i])); } return 0; }