BZOJ1857 [Scoi2010]传送带【三分法】

题目链接

题解

画画图就发现实际上是在\(AB\)上和\(CD\)上分别选两个点\(E\),\(F\)，使得\(t_{AE} + t_{EF} + t_{FD}\)最小

然后猜想到当\(E\)固定时，这个值的函数关于\(|CF|\)是下凸的

当\(F\)总取最优时，关于\(|AE|\)也是下凸的

感觉十分的对

两层三分即可

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

struct point{

	double x,y;

}A,B,C,D,AB,CD;

inline point operator -(const point& a,const point& b){

    return (point){a.x - b.x,a.y - b.y};

}

inline point operator +(const point& a,const point& b){

    return (point){a.x + b.x,a.y + b.y};

}

inline point operator *(const double& a,const point& b){

	return (point){a * b.x,a * b.y};

}

double dis(const point& a,const point& b){

	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

}

double P,Q,R;

double cal2(double lam1,double lam2){

	point E = A + lam1 * AB,F = C + lam2 * CD;

	return dis(A,E) / P + dis(E,F) / R + dis(F,D) / Q;

}

double cal(double lam){

	double l = 0,r = 1,lmid,rmid,len,cl,cr;

	while (r - l > 0.00001){

		len = r - l;

		lmid = l + len / 3;

		rmid = r - len / 3;

		cl = cal2(lam,lmid); cr = cal2(lam,rmid);

		if (cl > cr) l = lmid;

		else r = rmid;

	}

	return cal2(lam,(r + l) / 2);

}

int main(){

	scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y,&P,&Q,&R);

	AB = B - A; CD = D - C;

	double l = 0,r = 1,lmid,rmid,len,cl,cr;

	while (r - l > 0.00001){

		len = r - l;

		lmid = l + len / 3;

		rmid = r - len / 3;

		cl = cal(lmid); cr = cal(rmid);

		if (cl > cr) l = lmid;

		else r = rmid;

	}

	printf("%.2lf\n",cal((l + r) / 2));

	return 0;

}

巴特西

BZOJ1857 [Scoi2010]传送带【三分法】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ1857 [Scoi2010]传送带 【三分法】

题目链接

题解

最新文章

热门文章

BZOJ1857 [Scoi2010]传送带【三分法】