三分与模拟退火

acm

三分

三分最主要的是要是一个凸函数或者一个凹函数.

B - Texas Trip POJ - 3301

旋转点,然后正方形的边长就是连max(x差,y差).

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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int inf = 1<<28;
const int maxn = 44;
const double eps = 1e-9;

struct node{
    double x,y;
}p[maxn];
int n;
double cal(double ang){
    double ax,ay,bx,by;
    ax = ay = inf; bx = by = -inf;
    for(int i = 0; i < n; i++){
        double x = p[i].x * cos(ang) - p[i].y * sin(ang);
        double y = p[i].x * sin(ang) + p[i].y * cos(ang);
        ax = min(ax, x); ay = min(ay, y);
        bx = max(bx, x); by = max(by, y);
    }
    return max(bx-ax, by-ay);
}

int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%lf%lf",&p[i].x, &p[i].y);
        }
        double ans, l = 0, r = asin(1.0);
        for(int i = 0; i < 100; i++){
            double mid1 = l + (r - l)/3;
            double mid2 = r - (r - l)/3;
            if( cal(mid1) <= cal(mid2) ){
                r = mid2;
            } else {
                l = mid1;
            }
        }
        ans = cal(l);
        printf("%.2lf\n",ans*ans);
    }
}

A - Stealing a Cake HDU - 4454

本题可以枚举5000个点跑一下也能过.

考虑三分的话,我们发现随着角度的变化,他一定是一个凹函数+一个凸函数, 我们分两段跑圆的三分,一段是[0,pi],一段是[pi,pi*2],.不违背三分.

然后我想了一下,他肯定是一个凹函数+一个凸函数,一个函数都是由cosa,sina构成的,虽然有波折,但一定是有一个极大值,一个极小值.用我下面的二分是没有问题的,但如果使用的是mid = (l+r)/2; midd = (mid + r)/2 就可能会错.因为极小值就可能出现在(l,mid)中间,而如果cal(mid) 恰好大于cal(midd),就错了.

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
#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;
const double PI = acos(-1.0);

const double eps = 1e-9;
struct Point{
    double x,y;
}ant;

struct circle{
    double x,y,r;
}cake;

//rect

double x1,x2,x3,x4,yy1,y2,y3,y4;

double dis(double x1, double y1, double x2, double y2){
    return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
}

double cal(double ang){
    double x = cake.x + cake.r * cos(ang);
    double y = cake.y + cake.r * sin(ang);

    double ans = dis(ant.x, ant.y , x, y);
    double minx;
    if( (x1-x)*(x3-x) <= 0){
        minx = min(fabs(y - yy1), fabs(y - y3));
    }else if( (yy1-y)*(y3-y) <=0 ){
        minx = min(fabs(x - x1), fabs(x - x3));
    }else{
        minx = min(dis(x, y, x1, yy1), dis(x, y, x2, y2));
        minx = min(minx, dis(x, y, x3, y3));
        minx = min(minx, dis(x, y, x4, y4));
    }

    return ans + minx;
}

int main(){
    while(~scanf("%lf%lf",&ant.x,&ant.y)){
        if(fabs(ant.x) < eps && fabs(ant.y) < eps)break;
        scanf("%lf%lf%lf",&cake.x,&cake.y,&cake.r);
        scanf("%lf%lf%lf%lf",&x1,&yy1,&x3,&y3);
        x2 = x1; y2 = y3;
        x4 = x3; y4 = yy1;
        double l = 0 , r = PI*2, mid1, mid2;
        for(int i = 0; i < 200; i++){
            mid1 = l + (r-l)/3;
            mid2 = r - (r-l)/3;
            if(cal(mid1) < cal(mid2)){
                r = mid2;
            }else{
                l = mid1;
            }
        }
        double ans = cal(l);
        ans = min(ans, cal(l));
        printf("%.2lf\n",ans);
    }
    return 0;
}

F - Turn the cornerHDU - 2438

做多了就是水题

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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-9;

double x,y,l,d;

struct Point {
    double x,y;
    Point(){}
    Point(double x, double y):x(x),y(y){}
};

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

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

inline double Dist_Point_Seg(Point p,Point a,Point b){
    Point t=p;
    t.x+=a.y-b.y;t.y+=b.x-a.x;
    return fabs(Multi(p,a,b))/dis(a,b);
}
Point it;
double cal(double ang){
    double a,b;
    a = cos(ang)*l;
    b = sin(ang)*l;
    return Dist_Point_Seg(it, Point(a,0.0), Point(0.0,b));
}

int main(){
    while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&d)){
        it.x = x;it.y = y;
        double l = 0, r = PI/2, mid1, mid2;
        if(x<d || y <d){
            puts("no");
            continue;
        }
        for(int i = 0; i < 200; i++){
            mid1 = l + (r - l)/3;
            mid2 = r - (r - l)/3;
            if(cal(mid1) < cal(mid2)){
                r = mid2;
            }else{
                l = mid1;
            }
        }
        if(cal(l) < d)puts("no");
        else puts("yes");
    }
    return 0;
}

黄金分割法

记忆化了上一次的cal()值省去了一次计算．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const double phi=(sqrt(5.0)-1)/2;
double l = 0, r = 2*PI, mid1, mid2,f1=0,f2=100;
int left = 0,right = 0;
for(int i = 0; i < 35 && fabs(l-r)> 1e-5; i++){
  if(!left)mid1 = r - (r-l)*phi, f1 = cal(mid1);
  if(!right)mid2 = l + (r-l)*phi, f2 = cal(mid2);
  //cout << l << endl;
  if(f1 < f2){
    r = mid2; mid2 = mid1;left = 0; right = 1; f2 = f1;
  }
  else{
    l = mid1; mid1 = mid2; right = 0; left = 1; f1 = f2;
  }
}
//double ans = cal(l);
printf("%.7lf\n",f1);

模拟退火

不想学,什么垃圾玩意,复杂度都看不出来,eps全凭运气过.

附上acdream的

费马点问题求解 给n个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。

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
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define N 1005
#define eps 1e-8     //搜索停止条件阀值
#define INF 1e99     
#define delta 0.98   //温度下降速度
#define T 100        //初始温度

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};  //上下左右四个方向

struct Point
{
	double x, y;
};

Point p[N];

double dist(Point A, Point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double GetSum(Point p[], int n, Point t)
{
	double ans = 0;
	while(n--)
		ans += dist(p[n], t);
	return ans;
}

//其实我觉得这玩意儿根本不叫模拟退火
double Search(Point p[], int n)
{
	Point s = p[0];    //随机初始化一个点开始搜索
	double t = T;      //初始化温度
	double ans = INF;  //初始答案值
	while(t > eps)
	{
		bool flag = 1;
		while(flag)
		{
			flag = 0;
		    for(int i = 0; i < 4; i++)    //上下左右四个方向
		    {
			    Point z;
			    z.x = s.x + dx[i] * t;
			    z.y = s.y + dy[i] * t;
			    double tp = GetSum(p, n, z);
		        if(ans > tp)
				{
					ans = tp;
					s = z;
					flag = 1;
				}
		    }
		}
		t *= delta;
	}
	return ans;
}

int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		for(int i = 0; i < n; i++)
			scanf("%lf %lf", &p[i].x, &p[i].y);
		printf("%.0lf\n", Search(p, n));
	}
	return 0;
}

平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小。

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
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define N 1005
#define eps 1e-8     //搜索停止条件阀值
#define INF 1e99     
#define delta 0.98   //温度下降速度
#define T 100        //初始温度

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};  //上下左右四个方向

struct Point
{
	double x, y;
};

Point s[N], t[N];

double cross(Point A, Point B, Point C)  
{  
	return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);  
}  

double multi(Point A, Point B, Point C)  
{  
	return (B.x - A.x) * (C.x - A.x) + (B.y - A.y) * (C.y - A.y);  
}  

double dist(Point A, Point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double GetDist(Point A, Point B, Point C)  
{  
	if(dist(A, B) < eps) return dist(B, C);  
	if(multi(A, B, C) < -eps) return dist(A, C);  
	if(multi(B, A, C) < -eps) return dist(B, C);  
	return fabs(cross(A, B, C) / dist(A, B));  
}  

double GetSum(Point s[], Point t[], int n, Point o)
{
	double ans = 0;
	while(n--)
		ans += GetDist(s[n], t[n], o);
	return ans;
}

double Search(Point s[], Point t[], int n, Point &o)
{
	o = s[0];    
	double tem = T;      
	double ans = INF;
	while(tem > eps)
	{
		bool flag = 1;
		while(flag)
		{
			flag = 0;
		    for(int i = 0; i < 4; i++)    //上下左右四个方向
		    {
			    Point z;
			    z.x = o.x + dx[i] * tem;
			    z.y = o.y + dy[i] * tem;
			    double tp = GetSum(s, t, n, z);
		        if(ans > tp)
				{
					ans = tp;
					o = z;
					flag = 1;
				}
		    }
		}
		tem *= delta;
	}
	return ans;
}

int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		for(int i = 0; i < n; i++)
			scanf("%lf %lf %lf %lf", &s[i].x, &s[i].y, &t[i].x, &t[i].y);
		Point o;
		double ans = Search(s, t, n, o);
		printf("%.1lf %.1lf %.1lf\n", o.x, o.y, ans);  
	}
	return 0;
}

给定三维空间的n点，找出一个半径最小的球把这些点全部包围住。

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
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>

#define N 55
#define eps 1e-7
#define T 100
#define delta 0.98
#define INF 1e99

using namespace std;

struct Point
{
	double x, y, z;
};

Point p[N];

double dist(Point A, Point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) + (A.z - B.z) * (A.z - B.z));
}

double Search(Point p[], int n)
{
	Point s = p[0];
	double t = T;
	double ans = INF;
	while(t > eps)
	{
		int k = 0;
		for(int i = 0; i < n; i++)
			if(dist(s, p[i]) > dist(s, p[k]))
				k = i;
		double d = dist(s, p[k]);
		ans = min(ans, d);
		s.x += (p[k].x - s.x) / d * t;
		s.y += (p[k].y - s.y) / d * t;
		s.z += (p[k].z - s.z) / d * t;
		t *= delta;
	}
    return ans;
}

int main()
{
	int n;
    while(cin >> n && n)
	{
		for(int i = 0; i < n; i++)
			cin >> p[i].x >> p[i].y >> p[i].z;
		double ans = Search(p, n);
		printf("%.5lf\n", ans);
	}
	return 0;
}

函数最值问题求解

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
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define ITERS 10
#define T 100
#define eps 1e-8
#define delta 0.98
#define INF 1e99

using namespace std;

double x[ITERS];

int Judge(double x, double y)
{
	if(fabs(x - y) < eps) return 0;
	return x < y ? -1 : 1;
}

double Random()
{
	double x = rand() * 1.0 / RAND_MAX;
	if(rand() & 1) x *= -1;
	return x;
}

double F(double x, double y)
{
	return 6 * x * x * x * x * x * x * x + 8 * x * x * x * x * x * x + 7 * x * x * x + 5 * x * x - y * x;
}

void Init()
{
	for(int i = 0; i < ITERS; i++)
		x[i] = fabs(Random()) * 100;
}

double SA(double y)
{
	double ans = INF;
	double t = T;
	while(t > eps)
	{
		for(int i = 0; i < ITERS; i++)
		{
			double tmp = F(x[i], y);
			for(int j = 0; j < ITERS; j++)
			{
				double _x = x[i] + Random() * t;
				if(Judge(_x, 0) >= 0 && Judge(_x, 100) <= 0)
				{
					double f = F(_x, y);
					if(tmp > f) 
					    x[i] = _x;
				}
			} 
		}
		t *= delta;
	}
	for(int i = 0; i < ITERS; i++)
		ans = min(ans, F(x[i], y));
	return ans;
}

int main()
{
    int t;
	scanf("%d", &t);
	while(t--)
	{
		double y;
		scanf("%lf", &y);
		srand(time(NULL));
		Init();
		printf("%.4lf\n", SA(y));
	}
	return 0;
}

本文标题:三分与模拟退火

文章作者:呼哧

发布时间:2017-08-10, 11:40:42

最后更新:2018-08-04, 02:48:00

原始链接:http://hu-chi.github.io/2017/08/10/acm/三分与退火模拟/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 三分
    1. 1.1. B - Texas Trip POJ - 3301
    2. 1.2. A - Stealing a Cake HDU - 4454
    3. 1.3. F - Turn the cornerHDU - 2438
    4. 1.4. 黄金分割法
    5. 1.5. 模拟退火
      1. 1.5.1. 费马点问题求解 给n个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。
      2. 1.5.2. 平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小。
      3. 1.5.3. 给定三维空间的n点，找出一个半径最小的球把这些点全部包围住。
      4. 1.5.4. 函数最值问题求解
|