三分查找技术.doc

【标准化说明】三分查找技术与简单应用 三分查找技术适用于答案在某一个区间内，这个区间的特点的是，以答案为分点的两侧区间都单调的增大或者减小：如右图就是一个分的例子：三分的区间为l,r 其中最低点为答案每次把区间分为3个等分取x1=l+(r-l)/3 ,x2=r-(r-l)/3 作为分点，看谁更接近标准答案，并以此来更新左右区间，继续进行二分，直到得到(无限逼近)答案。Trick or TreatDescriptionJohnny and his friends have decided to spend Halloween night doing the usual candy collection from the households of their village. As the village is too big for a single group to collect the candy from all houses sequentially, Johnny and his friends have decided to split up so that each of them goes to a different house, collects the candy (or wreaks havoc if the residents dont give out candy), and returns to a meeting point arranged in advance. There are n houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnnys gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnnys interest is in eating the candy as soon as possible. Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line y = 0. Note that there may be houses on both sides of the river, and some of the houses may be houseboats (y = 0). The walking speed of every child is 1 meter per second, and they can move along any direction on the plane. At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy. Input Each test case starts with a line indicating the number n of houses ( 1n50 000). The next n lines describe the positions of the houses; each of these lines contains two floating point numbers x and y ( -200 000 x, y 200 000), the coordinates of a house in meters. All houses are at different positions. A blank line follows each case. A line with n = 0 indicates the end of the input; do not write any output for this case. Output For each test case, print two numbers in a line separated by a space: the coordinate x of the meeting point on the line y = 0 that minimizes the time the last child arrives, and this time itself (measured in seconds after midnight). Your answer should be accurate to within an absolute or relative error of 10-5. Sample Input 21.5 1.53 010 041 44 4-3 32 454 7-4 07 -6-2 48 -50Sample Output 1.500000000 1.5000000000.000000000 0.0000000001.000000000 5.0000000003.136363636 7.136363636SourceSouthwestern 2009-2010#include #include #include #include using namespace std;const int max_size=50001;struct point_type double x,y;int n;point_type pointmax_size;double l,r; /l-most left point (x_door) r-most right point (x_door)int cnt;void init() cnt=0; int i; for (i=1;i=n;i+) scanf(%lf %lf,&pointi.x,&pointi.y); l=r=point1.x; for (i=2;i=n;i+) if (pointi.xr) r=pointi.x; double E(double x) return x*x;double calc(double x) int i; double temp=0; for (i=1;itemp) temp=sqrt(E(pointi.x-x)+E(pointi.y); return temp;void solve() double _lp,_rp; double dist_l,dist_r; for (;r-l10e-12;) if (+cnt=64) break; _lp=l+(r-l)/3; _rp=r-(r-l)/3; dist_l=calc(_lp); dist_r=calc(_rp); if (dist_ldist_r) l=_lp