\(Pty plays game\)

题目大意

玩家有 \(n\) 个士兵， \(BOSS\) 有 \(m\) 个士兵，两边的士兵站成一个队列。

游戏过程如下：

• 两边队头的士兵相互攻击，当一名士兵阵亡时，他所在队列的下一个士兵会替补登场，若 \(BOSS\) 的士兵全部阵亡而玩家的士兵还活着，玩家胜利。

• 每个士兵有 \(h\) 的生命值，单位时间内能对敌造成的伤害为 \(d\) 。

开战之前，可以选择 \(x\) 天的训练时间，每训练一天，士兵 \(x\) 的生命值与攻击力会增长 \(dh_x\)与\(dd_x\) 。

问是否 \(\exists x\in [0,10^{18}]\) 使得玩家胜利，若存在，输出最小的 \(x\) ，否则，输出 \(none\) 。

分析

首先，对于这道题目，我们很容易向二分的方向去想，但我们并不知道其是否具有单调性，同时，我们不能在短时间内判断一个局面合法与否，考虑一次解决这些问题。

判断局面胜败

首先，我们注意到，如果玩家和 \(BOSS\) 都只有一个士兵，分别为 \((h_1,d_1)\),\((h_2,d_2)\) 则玩家打死 \(BOSS\) 的士兵所用的时间 \(T_1=\frac{h_2}{d_1}\) ，同理， \(BOSS\) 打死玩家的士兵所用的时间为 \(T_2=\frac{h_1}{d_2}\) 。

当 \(T_1<T_2\) 即 \(h_1\times d_1>h_2\times d_2\) 时，玩家将取得胜利。

考虑扩展这个局面，给 \(BOOS\) 增加一个士兵为 \((h_3,d_3)\) ，而战胜 \(BOSS\) 第一个士兵后，玩家的士兵状态变为 \((h_1-\frac{h_2}{d_1}\times d_2,d_1)\) 。

重复上面的过程，式子展开后我们发现玩家想要获胜需要 \(h_1\times d_1>h_2\times d_2+h_3\times d_3\) 。

那么一般的，若一个局面满足：

\[h_1\times d_1+h_2\times d_2+……+h_n\times d_n>h_{n+1}\times d_{n+1}+h_{n+2}\times d_{n+2}+……+h_{n+m}\times d_{n+m} \]

则玩家获胜。

化简求值

那么，对于一个合法的 \(x\) ，满足\(\sum_{i=1}^n (h_i+x\times dh_i)\times(d_i+x\times dd_i)>\sum_{i=n+1}^{n+m} (h_i+x\times dh_i)\times(d_i+x\times dd_i)\)

发现可以把两边展开，化为一个二次函数 \(Ax^2+Bx+C>0\) ，求满足条件的最小 \(x\)。

于是我们可以展开分类讨论，进行求解。

• 当 \(A\neq 0\) 时二次函数需要用到二分查找(当然也可以直接求根公式，如果你能把精度卡过的话)。

• 当 \(A=0\) 时一次函数可以直接求根，注意如果是小数应该向哪边取整。

• 当 \(A=0\) 且 \(B=0\) 时，函数值不变，直接看 \(C\) 即可。

注：注意精度

CODE

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10; 
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w*=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w; 
}
struct node{
	int x,y,dx,dy;
}a[N],b[N];
int T;
signed main()
{
//	freopen("data1.in","r",stdin);
//	freopen("data.out","w",stdout);
	T=read();
	while(T--){
		int n=read(),m=read();
		for(register int i=1;i<=n;i++){
			a[i].x=read(),a[i].dx=read();
			a[i].y=read(),a[i].dy=read();
		}
		for(register int i=1;i<=m;i++){
			b[i].x=read(),b[i].dx=read();
			b[i].y=read(),b[i].dy=read(); 
		}
		int A=0,B=0,C=0;
		for(register int i=1;i<=n;i++){
			A=A+a[i].dx*a[i].dy;
			B=B+a[i].y*a[i].dx+a[i].x*a[i].dy;
			C=C+a[i].x*a[i].y;
		}
		for(register int i=1;i<=m;i++){
			A=A-b[i].dx*b[i].dy;
			B=B-b[i].y*b[i].dx-b[i].x*b[i].dy;
			C=C-b[i].x*b[i].y;
		}
	//	printf("%lld %lld %lld\n",A,B,C);
		if(!A&&!B){
			if(C>0) puts("0");
			else puts("none");
			continue;
		}
		if(!A){
			int ans=(-C)/B;
			if(B>0){
				ans++;
				if(C>0) puts("0");
				else if(C==0) puts("1");
				else printf("%lld\n",ans);
			}
			else{
				if(C>0) puts("0");
				else puts("none");
			}
		}
		else{
			if(A>0){
				if(C>0) puts("0");
				else{
					long double l=0,r=1e18;
					int ans=-1;
					while(l<=r){
						int mid=(l+r)/2;
						if(A*(long double)mid*(long double)mid+B*(long double)mid+C>0) ans=mid,r=mid-1;
						else l=mid+1;
					}
					if(ans==-1) puts("none");
					else printf("%lld\n",ans);
				}
			}
			else{
				if(C>0) puts("0");
				else{
					double p=-(double)B/(double)(2*A);
					if(p<0) puts("none"); //对称轴小于0 
					else{
						double mx=(double)A*p*p+(double)B*p+C;
						//if(mx<0) { puts("none");
						long double l=0,r=(int)p;
						int ans=-1;
						while(l<=r){
							int mid=(l+r)/2;
							if(A*(long double)mid*(long double)mid+B*(long double)mid+C>0) ans=mid,r=mid-1;
							else l=mid+1;
						}
						if(ans==-1) puts("none");
						else printf("%lld\n",ans);
					}
				}
			}
		}
	}
	return 0;
}