【BZOJ 1857】【SCOI 2010】传送带

本文主要是介绍【BZOJ 1857】【SCOI 2010】传送带，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

做两次三分，第一次三分第一条线段上走出去的点，第二次三分第二条线段上到达的点。
证明这里就不写了，一堆三角函数。。。。反正一阶导数求出来一个过原点的二次函数，一开始是正，后来变成负，所以原函数是个凹函数（还是叫下凸函数？？）
我一开始很鸡冻啊！为啥啊？导数直接取0不就好了？对啊是直接可以求出那条斜线和两条直线的夹角的，但是还要考虑这个角度能不能取到，还要考虑两条直线本身和坐标轴的夹角······算了我还是三分吧。。。。
话说我这里的三分竟然是。。。三等分？（滑稽）

#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 100000
#define eps 1e-3
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
int ax,ay,bx,by,cx,cy,dx,dy;
int p,q,r;
double dis(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
double calc(double x,double y)
{double lx = cx , ly = cy , rx = dx , ry = dy;double x1,y1,x2,y2,t1,t2;while (fabs(rx-lx) > eps || fabs(ry-ly) > eps){x1 = lx + (rx - lx) / 3; y1 = ly + (ry - ly) / 3;x2 = x1 + (rx - lx) / 3; y2 = y1 + (ry - ly) / 3;t1 = dis(ax,ay,x,y) / p + dis(x,y,x1,y1) / r + dis(x1,y1,dx,dy) / q;t2 = dis(ax,ay,x,y) / p + dis(x,y,x2,y2) / r + dis(x2,y2,dx,dy) / q;if (t1 > t2) {lx = x1; ly = y1;} else {rx = x2; ry = y2;}}return dis(ax,ay,x,y) / p + dis(x,y,lx,ly) / r + dis(lx,ly,dx,dy) / q;
}int main()
{scanf("%d%d%d%d",&ax,&ay,&bx,&by);scanf("%d%d%d%d",&cx,&cy,&dx,&dy);scanf("%d%d%d",&p,&q,&r);double lx = ax , ly = ay , rx = bx , ry = by;double x1,y1,x2,y2,t1,t2;while (fabs(rx-lx)>eps || fabs(ry-ly)>eps){x1 = lx + (rx - lx) / 3; y1 = ly + (ry - ly) / 3;x2 = x1 + (rx - lx) / 3; y2 = y1 + (ry - ly) / 3;t1 = calc(x1,y1); t2 = calc(x2,y2);if (t1 > t2) {lx = x1; ly = y1;} else {rx = x2; ry = y2;}}printf("%.2lf\n",calc(lx,ly));return 0;
}