【BZOJ1857】【SCOI2010】传送带（三分套三分）

三分的第一道入手题。

三分是个什么样的东西呢？我用一个例题来解释：

给你一段序列，保证有且仅有一个位置 \(i\)，使得 \(i\) 左边的序列单调递增，\(i\) 右边的序列单调递减，请你找出这个位置 \(i\)

这个问题形象的解释就是有一座山峰，问你这座山峰的最高点在哪里。

那么我们可以用到三分法来解决。三分像二分一样，有一个询问区间 \(l\)、\(r\)，也就是我们确定答案就在这个区间内。我们每次先像二分一样求出 \(mid\)，然后我们找出两个数：\(mid_l\)、\(mid_r\)，分别为 \(mid\) 的左边一位上的数和右边一位上的数，然后比较 \(mid_l\) 和 \(mid_r\) 的大小。由于从 \(mid_l\) 到 \(mid_r\) 肯定是单调递增的（除非 \(mid\) 就是我们要找的那个数，这种情况要特判），所以若 \(mid_l<mid_r\)，则我们要找的位置肯定在 \(l\sim mid_r\) 之间，所以 \(r=mid_r\)。否则就是 \(l=mid_l\)。

那么这一题怎么做呢？我们用三分套三分，第一个三分枚举第一条线段上的转向点 \(M\)，第二个三分枚举第二条线段上的转向点 \(N\)。

代码如下：

#include<bits/stdc++.h>

#define eps 1e-4

using namespace std;

struct Point
{
	double x,y;
	void read()
	{
		scanf("%lf%lf",&x,&y);
	}
	void write()
	{
		printf("%lf %lf\n",x,y);
	}
	Point(){};
	Point(double xx,double yy)
	{
		x=xx,y=yy;
	}
}a,b,c,d;

bool operator == (Point a,Point b)
{
	return a.x==b.x&&a.y==b.y;
}

struct Line
{
	double k,b;
	void get(Point p1,Point p2)
	{
		k=(p1.y-p2.y)/(p1.x-p2.x);
		b=p1.y-k*p1.x;
	}
}AB,CD;

double p,q,r,ans;

double find1(Line l,double x)
{
	return l.k*x+l.b;
}

double dis(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double calc2(Point p1,Point p2)
{
	return dis(p1,p2)/r+dis(p2,d)/q;
}

double calc1(Point p1)
{
	if(c==d)
		return dis(a,p1)/p+dis(p1,c)/r;
	double ans;
	if(c.x!=d.x)
	{
		double l=c.x,r=d.x,ans;
		if(l>r)swap(l,r);
		while(r-l>eps)
		{
			double mid=(l+r)/2.0;
			double mid1=mid-eps/2.0,mid2=mid+eps/2.0;
			double dis1=calc2(p1,Point(mid1,c.y!=d.y?find1(CD,mid1):c.y));
			double dis2=calc2(p1,Point(mid2,c.y!=d.y?find1(CD,mid2):c.y));
			if(dis1<dis2)
				ans=dis1,r=mid-eps;
			else
				ans=dis2,l=mid+eps;
		}
		return dis(a,p1)/p+ans;
	}
	else
	{
		double l=c.y,r=d.y,ans=0;
		if(l>r)swap(l,r);
		while(r-l>eps)
		{
			double mid=(l+r)/2.0;
			double mid1=mid-eps/2.0,mid2=mid+eps/2.0;
			double dis1=calc2(p1,Point(c.x,mid1));
			double dis2=calc2(p1,Point(c.x,mid2));
			if(dis1<dis2)
				ans=dis1,r=mid-eps;
			else
				ans=dis2,l=mid+eps;
		}
		return dis(a,p1)/p+ans;
	}
}

int main()
{
	a.read(),b.read(),c.read(),d.read();
	AB.get(a,b),CD.get(c,d);
	scanf("%lf%lf%lf",&p,&q,&r);
	if(a==b&&c==d)
	{
		printf("%.2lf\n",dis(a,c));
		return 0;
	}
	if(a==b)
	{
		printf("%.2lf\n",calc1(a));
		return 0;
	}
	double ans;
	if(a.x!=b.x)
	{
		double l=a.x,r=b.x;
		if(l>r)swap(l,r);
		while(r-l>eps)
		{
			double mid=(l+r)/2.0;
			double mid1=mid-eps/2.0,mid2=mid+eps/2.0;
			double dis1=calc1(Point(mid1,a.y!=b.y?find1(AB,mid1):a.y));
			double dis2=calc1(Point(mid2,a.y!=b.y?find1(AB,mid2):a.y));
			if(dis1<dis2)
				ans=dis1,r=mid-eps;
			else 
				ans=dis2,l=mid+eps;
		}
	}
	else
	{
		double l=a.y,r=b.y;
		if(l>r)swap(l,r);
		while(r-l>eps)
		{
			double mid=(l+r)/2.0;
			double mid1=mid-eps/2.0,mid2=mid+eps/2.0;
			double dis1=calc1(Point(a.x,mid1));
			double dis2=calc1(Point(a.x,mid2));
			if(dis1<dis2)
				ans=dis1,r=mid-eps;
			else 
				ans=dis2,l=mid+eps;
		}
	}
	printf("%.2lf\n",ans);
}
/*
0 0 0 100
100 0 100 100
2 2 1
*/

原文地址：http://www.cnblogs.com/ez-lcw/p/16837099.html