Gym - 100886D 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest D - Catenary

题目中有一句很迷幻的话：这是对双曲余弦函数的离散模拟
翻译成人话就是长成下图这样的图形就别考虑了，总体上还是和双曲余弦函数图像比较像的

双曲余弦函数在这种情况下也可以叫悬链线，很容易可以查到相关资料（不过对于这题没啥帮助）

根据题目的需求，把图形翻转一下得到向上垂的图形
因为铰链连接的木棍，在连接点上力的方向不一定沿杆的方向，所以需要对力的方向进行分析
下图黑色是木棍，红色是力的方向

记从x轴转到经过第i个点的力方向经过的夹角为$\varphi_i$φi​，约定i从0开始，在这里的力的方向都是从标号小的点指向标号大的
（所以$\varphi$φ会从正值逐渐变成负值）
考虑任意一段木棍（至少一根）只有两端的力是外力（在这里以上图4根棍举例，点标号0-4，棍标号1-4）
竖直方向：$F\sin\varphi_0-F\sin\varphi_n=G_{[1,4]}$Fsinφ0​−Fsinφn​=G[1,4]​（G是重力）
因为每个连接点都平衡，则有$F_i\cos\varphi_i=c$Fi​cosφi​=c（c是常数）
用上面两条式子一除，就有$\tan\varphi_0-\tan\varphi_4=\frac{G_{[1,4]}} c$tanφ0​−tanφ4​=cG[1,4]​​
（上式0，4可推广到任意两端点依然成立）
$\tan\varphi_i-\tan\varphi_j=\frac{G_{[i+1,j]}} c$tanφi​−tanφj​=cG[i+1,j]​​

再考虑一下单个木棍的平衡，下图中蓝色是棍，红色是力的方向。
三力方向必共点，不然选择任两力交点作为支点，第三力到支点力矩不为0，木棍不平衡。
则结合木棍重心在中点的性质，可以很轻松地得到$\tan\theta=\frac{\tan\varphi_1+\tan\varphi_2}{2}$tanθ=2tanφ1​+tanφ2​​

考虑一下怎么把两条式子合起来，很显然可以做差
$\tan\varphi_{i-1}-\tan\varphi_n+\tan\varphi_{i}-\tan\varphi_{n-1}=\tan\theta_i-\tan\theta_{n-1}=(G_{[i,n]}+G_{[i+1,n-1]})*\frac2c$tanφi−1​−tanφn​+tanφi​−tanφn−1​=tanθi​−tanθn−1​=(G[i,n]​+G[i+1,n−1]​)∗c2​

接下来这段感性认识一下
这东西翘的越高就会越窄，而角度都由首尾两个角决定。那么二分套二分，
在第一个角固定的前提下，最后一个角越翘，最后的点就会越高。
那么二分的目标就是让最后一个点回归水平
第一个角越翘，那么整体就会越窄
所以这个二分就是要让整体宽度接近L

二分后先把c算出来，再用上面那条式子依次算出每个角tan值即可

#include<stdio.h>
#include<cmath>
const double pi=acos(-1);

int n;
double g[15],l[15],L,Tan[15];

inline double sqr(double x){return x*x;}
inline double Sin(double Tan){return (Tan>0?1:-1)*sqrt(sqr(Tan)/(1+sqr(Tan)));}
inline double Cos(double Tan){return sqrt(1/(1+sqr(Tan)));}

inline double solve(double tan0,double tann)
{
	double c=(tan0-tann)/(g[n]-g[0]+g[n-1]-g[1]),rt=0;
	for (int i=1;i<=n;i++) 
		rt+=l[i]*Sin(Tan[i]=tann+c*(g[n]-g[i-1]+g[n-1]-g[i]));
	return rt;
}

inline double judge(double th0)
{
	double _l=-pi/2,_r=0,rt=0;
	for (int ts=0;ts<100;ts++)
	{
		double mid=(_l+_r)/2;
		if (solve(tan(th0),tan(mid))>0) _r=mid;
		else _l=mid;
	}
	for (int i=1;i<=n;i++) rt+=l[i]*Cos(Tan[i]);
	return rt;
}

int main()
{
	scanf("%d%lf",&n,&L);
	for (int i=1;i<=n;i++) scanf("%lf",l+i),g[i]=g[i-1]+l[i];
	double _l=0,_r=pi/2;
	for (int ts=0;ts<100;ts++)
	{
		double mid=(_l+_r)/2;
		if (judge(mid)<L) _r=mid;
		else _l=mid;
	}
	double x=0,y=0;
	for (int i=1;i<n;i++) printf("%.10lf %.10lf\n",x+=l[i]*Cos(Tan[i]),y+=l[i]*Sin(Tan[i]));
}