三分

算法学习笔记(62): 三分法 - 知乎 (zhihu.com)

二分只适用于单调函数，三分用于单峰函数

用来求极值用的。

假如是一个向上凸的函数，求极大值

1
2
3
4
5
6
7
8
9
while (r - l > eps)
{
    mid = (l + r) / 2;
    double fl = f(mid - eps), fr = f(mid + eps);
    if (fl < fr)
        l = mid; 
    else
        r = mid;
}

三分套三分

先固定一个东西求三分，再固定一个东西求三分，最后得到答案，就是三分套三分了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
double f(double x, double y)
{
    return (x - 1) * (x - 1) + (x + y) * (x + y) + sin(y);
}
double run(double x) // 固定x，三分y
{
    double l = -4, r = 4, mid;
    while (r - l > eps)
    {
        mid = (l + r) / 2;
        if (f(x, mid - eps) > f(x, mid + eps))
            l = mid;
        else
            r = mid;
    }
    return f(x, mid);
}
int main()
{
    double l = -4, r = 4, mid, ans;
    while (r - l > eps)
    {
        mid = (l + r) / 2; // 三分x
        if (run(mid - eps) > run(mid + eps))
            l = mid;
        else
            r = mid;
    }
    printf("%.6f\n", run(mid)); // -0.918827
    return 0;
}

配套题目

A - Texas Trip

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of his SUV. The local American Tire store sells fiberglass patching material only in square sheets. What is the smallest patch that Harry needs to fix his door?

Assume that the holes are points on the integer lattice in the plane. Your job is to find the area of the smallest square that will cover all the holes.

Input

The first line of input contains a single integer T expressed in decimal with no leading zeroes, denoting the number of test cases to follow. The subsequent lines of input describe the test cases.

Each test case begins with a single line, containing a single integer n expressed in decimal with no leading zeroes, the number of points to follow; each of the following n lines contains two integers x and y, both expressed in decimal with no leading zeroes, giving the coordinates of one of your points.

You are guaranteed that T ≤ 30 and that no data set contains more than 30 points. All points in each data set will be no more than 500 units away from (0,0).

Output

Print, on a single line with two decimal places of precision, the area of the smallest square containing all of your points.

Sample

Inputcopy Outputcopy
2 4 -1 -1 1 -1 1 1 -1 1 4 10 1 10 -1 -10 1 -10 -1 4.00 242.00

选择角度作为我们的三分条件，很显然正方体要找到对角的两个点，因为对角的点最远。

但是，正方体可以是斜的，就是说可以不是平行于x,y轴。

可以康康样例二。

故需要翻转坐标系，所以想到三分角度。

翻转坐标系一个x角度的话，坐标会相应变化，如下：

(x,y)=(xcosθ−ysinθ,xsinθ+ycosθ)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// by Totoro
/*
while (r - l > eps)
{
    mid = (l + r) / 2;
    double fl = f(mid - eps), fr = f(mid + eps);
    if (fl < fr)
        l = mid; // 这里不写成mid - eps，防止死循环；可能会错过极值，但在误差范围以内所以没关系
    else
        r = mid;
}
*/
/*
double run(double x) // 固定x，三分y
{
    double l = -4, r = 4, mid;
    while (r - l > eps)
    {
        mid = (l + r) / 2;
        if (f(x, mid - eps) > f(x, mid + eps))
            l = mid;
        else
            r = mid;
    }
    return f(x, mid);
}
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
int n;
double inf=1e10;
const int N=1e6+100;
double x[N];
double y[N];
const double eps = 1e-8;
//精度
const double pi = acos(-1.0);
//求pi
double f(double t)
{
    double maxx = -inf, minx = inf, maxy = -inf, miny = inf;
    for (int i = 0; i < n; ++i)
    {
        maxx = max(maxx, x[i] * cos(t) - y[i] * sin(t));
        maxy = max(maxy, x[i] * sin(t) + y[i] * cos(t));
        miny = min(miny, x[i] * sin(t) + y[i] * cos(t));
        minx = min(minx, x[i] * cos(t) - y[i] * sin(t));
        //求出最大最小
    }
    return max(maxx - minx, maxy - miny);
}
int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t;
        cin >> t;
        while (t--)
        {
            cin >> n;
            rep(i, 0, n - 1)
            {
                cin >> x[i] >> y[i];
            }
            double l = 0;
            double r = pi ;
            double mid;
            while (r - l > eps)
            {
                mid = (l + r) / 2;
                if (f(mid - eps) > f(mid + eps))
                    l = mid;
                else
                    r = mid;
            }
            double ans = f(l);
            printf("%.2f\n", ans * ans);
            //输出面积
    }
    }

B - Line belt

In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww's speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane. How long must he take to travel from A to D?

Input

The first line is the case number T. For each case, there are three lines. The first line, four integers, the coordinates of A and B: Ax Ay Bx By. The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy. The third line, three integers, P Q R. 0<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000 1<=P，Q，R<=10

Output

The minimum time to travel from A to D, round to two decimals.

Sample

Inputcopy Outputcopy
1 0 0 0 100 100 0 100 100 2 2 1 136.60 
1
2
3
4
5
6
7
8
9
10
11
12
//本题有两条线段
//AB,CD
//显然路径要怎么走呢
//从A-E-F-D
//显然是这样
//根据三分的话
//应该是先三分E,再三分F
//三分AE在AB上的占比
//占比的枚举应该是从0-1开始的
//再三分CF在CD上的占比
//应该就可以做
//试一试

因此要用三分套三分，因为有两个地方需要你去控制（）

本题调了一个半小时，最后发现，eps不能写成1e-18，改成1e-8后一发入魂（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// by Totoro
/*
while (r - l > eps)
{
    mid = (l + r) / 2;
    double fl = f(mid - eps), fr = f(mid + eps);
    if (fl < fr)
        l = mid; // 这里不写成mid - eps，防止死循环；可能会错过极值，但在误差范围以内所以没关系
    else
        r = mid;
}
*/
/*
double run(double x) // 固定x，三分y
{
    double l = -4, r = 4, mid;
    while (r - l > eps)
    {
        mid = (l + r) / 2;
        if (f(x, mid - eps) > f(x, mid + eps))
            l = mid;
        else
            r = mid;
    }
    return f(x, mid);
}
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
double p, q, r;
double x_1, x2, y_1, y2;
double x3, x4, y3, y4;
double eps = 1e-8;
double juli(double x_1,double y_1,double x2,double y2)
{
    return sqrt((x_1-x2)*(x_1-x2)+(y_1-y2)*(y_1-y2));
}
double f(double x,double y)
{
double x5,x6,y5,y6;
x5=(x2-x_1)*x+x_1;
y5=(y2-y_1)*x+y_1;
x6=(x4-x3)*(1-y)+x3;
y6=(y4-y3)*(1-y)+y3;
double a=juli(x_1,y_1,x5,y5)/p;
double b=juli(x5,y5,x6,y6)/r;
double c=juli(x6,y6,x4,y4)/q;
double ans=a+b+c;
return ans;
}
double run(double x)
//占比为x
//已经固定了x了
{
double l=0;
double r=1;
double mid;
while(r-l>eps)
{
mid=(l+r)/2;
if(f(x,mid-eps)>f(x,mid+eps))
{
    l=mid;
}
else
{
    r=mid;
}
}
return f(x,mid);
}
void solve()
{
//本题有两条线段
//AB,CD
//显然路径要怎么走呢
//从A-E-F-D
//显然是这样
//根据三分的话
//应该是先三分E,再三分F
//三分AE在AB上的占比
//占比的枚举应该是从0-1开始的
//再三分CF在CD上的占比
//应该就可以做
//试一试
cin>>x_1>>y_1>>x2>>y2;
cin>>x3>>y3>>x4>>y4;
cin>>p>>q>>r;
double l=0;
double r=1;
double mid;
while(r-l>eps)
{
 mid=(r+l)/2;
if(run(mid-eps)>run(mid+eps))
{
    l=mid;
}
else
{
r=mid;
}
}
printf("%.2lf",run(mid));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin>>t;
    while (t--)
    {
        solve();
    }
}

C - Stealing a Cake

There is a big round cake on the ground. A small ant plans to steal a small piece of cake. He starts from a certain point, reaches the cake, and then carry the piece back home. He does not want to be detected, so he is going to design a shortest path to achieve his goal.

The big cake can be considered as a circle on a 2D plane. The ant’s home can be considered as a rectangle. The ant can walk through the cake. Please find out the shortest path for the poor ant.

Input

The input consists of several test cases. The first line of each test case contains x,y, representing the coordinate of the starting point. The second line contains x, y, r. The center of the cake is point (x,y) and the radius of the cake is r. The third line contains x1,y1,x2,y2, representing the coordinates of two opposite vertices of the rectangle --- the ant's home. All numbers in the input are real numbers range from -10000 to 10000. It is guaranteed that the cake and the ant's home don't overlap or contact, and the ant's starting point also is not inside the cake or his home, and doesn't contact with the cake or his home. If the ant touches any part of home, then he is at home. Input ends with a line of 0 0. There may be a blank line between two test cases.

Output

For each test case, print the shortest distance to achieve his goal. Please round the result to 2 digits after decimal point.

Sample

Inputcopy Outputcopy
1 1 -1 1 1 0 -1 1 0 0 2 -1 1 1 0 -1 1 0 0 0 1.75 2.00

C题其实和A题很像，只需要枚举圆上的点就可以，因此还是要三分角度啊，因为仍然是单峰函数。

三分这个反而很好写，主要是矩阵的距离判断比较繁琐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// by Totoro
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
const int N = 1e6 + 100;
double pi=acos(-1.0);
double eps = 1e-10;
double x, y, r;
double x_1, x_2, y_1, y_2;
double a, b;
double juli(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
//圆上面的点到矩形还有到那个点之间的距离
//矩形应该是要在边框才是罢
double f(double t)
{
double x_3=x+cos(t)*r;
double y_3=y+sin(t)*r;
double res=juli(x_3,y_3,a,b);
double ans;
if (x_3 < x_1)
{
    //如果同时在下方，到左下角的一个顶点
    if (y_3 < y_1)
        {
            ans = juli(x_1,y_1,x_3,y_3);
        }
        //如果在下方，但是在左右，那么是到横轴的距离
    else if (y_3 >= y_1 && y_3 <= y_2)
        {
            ans = x_1 - x_3;
        }
        //在下方，又在右边，那么就是右下角那个了
    else
        {
            ans = juli(x_1,y_2,x_3,y_3);
        }
}
//中间，比较一下y值就可以
else if (x_3 >= x_1 && x_3 <= x_2)
{
    if (y_3 < y_1)
        {
            ans = y_1 - y_3;
        }
    else
    {
            ans = y_3 - y_2;
    }
}
//在上面
else if (x_3 > x_2)
{
    if (y_3 < y_1)
        {
            ans = juli(x_2,y_1,x_3,y_3);
        }
    else if (y_3 >= y_1 && y_3 <= y_2)
        {
            ans = x_3 - x_2;
        }
    else
      {
            ans = juli(x_2,y_2,x_3,y_3);
      }  
}
return ans + res;
}
int main()
{
    while(cin>>a>>b)
    {
        if(a==0&&b==0)
        {
            return 0;
        }
cin>>x>>y>>r;
cin>>x_1>>y_1>>x_2>>y_2;
if(x_1>x_2)
{
swap(x_1,x_2);
}
if(y_1>y_2)
{
swap(y_1,y_2);
}
double l=0;
double r=2*pi;
double mid;
while(r-l>eps)
{
mid=(l+r)/2;
if(f(mid+eps)<f(mid-eps))
{
    l=mid;
}
else
{
    r=mid;
}
}
printf("%.2f\n",f(mid));
    }
}

采购还需加练啊（数论全都不会）