不知道哪来的题
样例输入
1 2 3 4样例输出
0.200000000000000数据
|a|,|b|,|c|,|d|<=1e9很多大佬迅速想到二分，但是我没有，我以为是结论题，所以算了个结论。
证明出
a n s = m a x ( m i n ( a ⋅ k − c k − 1 , a ⋅ k − c k + 1 ) , m i n ( b ⋅ k − d k − 1 , b ⋅ k − d k + 1 ) ) k ∈ R ans=max(min( \frac{a \cdot k-c}{k-1} , \frac{a \cdot k-c}{k+1} ),min( \frac{b \cdot k-d}{k-1} , \frac{b \cdot k-d}{k+1} )) \,\,\,\,\,\,\,\,\,k \in R ans=max(min(k−1a⋅k−c,k+1a⋅k−c),min(k−1b⋅k−d,k+1b⋅k−d))k∈R
求最小的 k \ k k。 其实可以看出是四个关于 k \ k k的函数。
f 1 ( k ) = a ⋅ k − c k − 1 f 2 ( k ) = a ⋅ k − c k + 1 f 3 ( k ) = b ⋅ k − d k − 1 f 4 ( k ) = b ⋅ k − d k + 1 f 5 ( k ) = − f 1 ( k ) f 6 ( k ) = − f 2 ( k ) f 7 = − f 3 ( k ) f 8 ( k ) = − f 4 ( k ) f_{1}(k)= \frac{a \cdot k-c}{k-1} \\ f_{2}(k)= \frac{a \cdot k-c}{k+1} \\ f_{3}(k)= \frac{b \cdot k-d}{k-1} \\ f_{4}(k)= \frac{b \cdot k-d}{k+1} \\ f_{5}(k)=-f_{1}(k)\,\,\,\,\,\,f_{6}(k)=-f_{2}(k)\,\,\,\,\,\,f_{7}=-f_{3}(k)\,\,\,\,\,\,f_{8}(k)=-f_{4}(k) f1(k)=k−1a⋅k−cf2(k)=k+1a⋅k−cf3(k)=k−1b⋅k−df4(k)=k+1b⋅k−df5(k)=−f1(k)f6(k)=−f2(k)f7=−f3(k)f8(k)=−f4(k)
易证答案在这几个函数的交点上，枚举每个交点即可： 复杂度O(小常数)
精度不高，好在题目不要求精度
#include<bits/stdc++.h> #define q1 a,a-c,-1.0 #define q2 b,b-d,-1.0 #define q3 -a,c-a,-1.0 #define q4 -b,d-b,-1.0 #define q5 a,-a-c,1.0 #define q6 b,-b-d,1.0 #define q7 -a,a+c,1.0 #define q8 -b,b+d,1.0//八个方程 using namespace std; double a,b,c,d; double ans=9999999999999; double ans1=0; double ans2=0; double geta(double a,double k1,double b,double c,double k2,double d)//解方程算交点 方程为a+k1/x+b = c+k2/x+d { double aa=a-c,bb=a*d+a*b+k1-c*d-c*b-k2,cc=a*b*d+k1*d-c*b*d-k2*b; double dd=bb*bb-4*aa*cc; if(dd>=0) { ans1=(-bb+sqrt(dd))/(2*aa); ans2=(-bb-sqrt(dd))/(2*aa); } } int main() { freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); cin>>a>>b>>c>>d; double k=0; geta(q1,q2); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q1,q3); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q1,q4); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q1,q5); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q1,q6); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q1,q7); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q1,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q2,q3); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q2,q4); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q2,q5); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q2,q6); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q2,q7); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q2,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q3,q4); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q3,q5); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q3,q6); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q3,q7); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q3,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q4,q5); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q4,q6); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q4,q7); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q4,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q5,q6); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q5,q7); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q5,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q6,q7); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q6,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); geta(q7,q8); k=ans1; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); k=ans2; ans=min(ans,max(min(fabs((1.0*a*k-c)/(k+1)),fabs((1.0*a*k-c)/(k-1))),min(fabs((1.0*b*k-d)/(k+1)),fabs((1.0*b*k-d)/(k-1))))); printf("%.15lf",ans); return 0; } /* 1996年：东方灵异传（TOH1） 1997年：东方封魔录（TOH2） 1997年：东方梦时空（TOH3） 1998年：东方幻想乡（TOH4） 1998年：东方怪绮谈（TOH5） 2002年：东方红魔乡（TOH6） 2003年：东方妖妖梦（TOH7） 2004年：东方萃梦想（TOH7.5） 2004年：东方永夜抄（TOH8） 2005年：东方花映冢（TOH9） 2005年：东方文花帖（TOH9.5） 2007年：东方风神录（TOH10） 2008年：东方绯想天（TOH10.5） 2008年：东方地灵殿（TOH11） 2009年：东方星莲船（TOH12） 2009年：东方非想天则（TOH12.3） 2010年：东方文花帖DS（TOH12.5） 2010年：东方三月精（TOH12.8） 2011年：东方神灵庙（TOH13） 2013年：东方心绮楼（TOH13.5） 2013年：东方辉针城（TOH14） 2014年：弹幕天邪鬼（TOH14.3） 2014年：东方深秘录（TOH14.5） 2015年：东方绀珠传（TOH15） 2017年：东方凭依华（TOH15.5） 2017年：东方天空璋（TOH16） */虽然是水过的题，不过依然感觉不错。
