HDU4688 Cut the Cake

2013多校, DP, HDU, 计算几何

　　2013 Multi-University Training Contest 9

　　题意：给定一个宽为w长为h的矩形，矩形中n个点组成凸多边形，按多边形的边每次将矩形一分为二，对凸多边形所在部分继续操作一分为二的操作，直至完全切割出凸多边形。若每一次切割的代价为切割线的长度，求最小代价。 - 原题链接

　　在网上搜到一位大佬的解题报告，持续懵逼… 看不懂init，看不懂dp，计算几何及dp渣渣啃了半天昏昏欲睡🌚

　　按输入顺序相邻两点p[i]和p[i+1]建边line[i]，分别记p[i]和p[i+1]为line[i]的左右端点，重点是理解以下数组的作用：

  • ld[i]：line[i]左端点到边界的最短距离（此处的距离是指，line[i]的左端点到line[i]与边界的交点的距离，下同）
  • rd[i]：line[i]右端点到边界的最短距离
  • rel[i][j]：line[i]左端点到line[j]更近为true，否则右端点更近，为false（此处的距离是指，line[i]的左端点到line[i]与line[j]的交点的距离，下同）
  • dd[i][j]：line[i]某端点到line[j]的最短距离（rel[i][j]为true是左端点，否则是右端点）

　　搞懂了init计算，剩下的dp过程就简单很多，f[i][j]表示其余边已经切割完成的前提下切割i~j-1所需要的最小代价，f[i][j]=f[i][k]+f[k+1][j]+cost(k)，为简化，点和边数组扩展一倍循环存储，详情见代码。 


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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=200+10;
const double inf=1e9, def=1e-9;
int n;
double w, h, ld[maxn], rd[maxn], dd[maxn][maxn], f[maxn][maxn];
bool rel[maxn][maxn], vis[maxn][maxn];
struct Point
{
	double x, y;
	Point(double _x=0, double _y=0)
	{
		x=_x, y=_y;
	}
	void sc()
	{
		scanf("%lf%lf", &x, &y);
	}
	double dis(Point t)
	{
		return sqrt((x-t.x)*(x-t.x)+(y-t.y)*(y-t.y));
	}
	double operator *(Point t)
	{
		return x*t.y-y*t.x;
	}
	Point operator -(Point t)
	{
		return Point(x-t.x, y-t.y);
	}
}p[maxn];
struct Line
{
	Point u, v;
	double len;
	Line(){}
	Line(Point _u, Point _v)
	{
		u=_u, v=_v, len=_u.dis(_v);
	}
	bool par(Line t)
	{
		return fabs((v-u)*(t.v-t.u))<=def;
	}
	Point inter(Line t)
	{
		double s1=(t.v-u)*(t.u-u), s2=(t.u-v)*(t.v-v);
		return Point((u.x*s2+v.x*s1)/(s1+s2), (u.y*s2+v.y*s1)/(s1+s2));
	}
}line[maxn];
void Init()
{
	for(int i=0; i<n*2; i++)
		for(int j=0; j<n*2; j++) if(i!=j)
		{
			if(line[i].par(line[j]))
			{
				rel[i][j]=true;
				dd[i][j]=inf;
			}
			else
			{
				Point o=line[i].inter(line[j]);
				double l=o.dis(p[i]), r=o.dis(p[i+1]);
				if(l<r)
				{
					rel[i][j]=true;
					dd[i][j]=l;
				}
				else
				{
					rel[i][j]=false;
					dd[i][j]=r;
				}
			}
		}
	Point g[5]={Point(0, 0), Point(w, 0), Point (w, h), Point(0, h), Point(0, 0)};
	for(int i=0; i<2*n; i++)
	{
		ld[i]=rd[i]=inf;
		for(int j=0; j<4; j++)
		{
			Line tp=Line(g[j], g[j+1]);
			if(!line[i].par(tp))
			{
				Point o=line[i].inter(tp);
				double l=o.dis(p[i]), r=o.dis(p[i+1]);
				if(l<r)	ld[i]=min(ld[i], l);
				else rd[i]=min(rd[i], r);
			}
		}
	}
	return ;
}
double DP(int i, int j)
{
	if(i>=j)	return 0;
	if(vis[i][j])	return f[i][j];
	f[i][j]=inf;
	vis[i][j]=true;
	for(int k=i; k<j; k++)
	{
		double l=ld[k], r=rd[k];
		if(rel[k][i-1])	l=min(l, dd[k][i-1]);	//前i-1条边已经处理好，如果到line[i]的距离比到边界的距离更近，cost中应该加上前者
		else r=min(r, dd[k][i-1]);
		if(rel[k][j])	l=min(l, dd[k][j]);
		else r=min(r, dd[k][j]);
		f[i][j]=min(f[i][j], DP(i, k)+DP(k+1, j)+l+r+line[k].len);
	}
	return f[i][j];
}
int main()
{
	while(scanf("%d%lf%lf", &n, &w, &h)!=EOF)
	{
		memset(vis, 0, sizeof vis);
		memset(rel, 0, sizeof rel);
		for(int i=0; i<n; i++)	p[i].sc();
		for(int i=n; i<=n*2; i++)	p[i]=p[i-n];	//i<=n*2
		for(int i=0; i<n*2; i++)	line[i]=Line(p[i], p[i+1]);
	
		double ans=inf;
		Init();
		for(int i=0; i<n; i++)	ans=min(ans, DP(i+1, i+n)+ld[i]+rd[i]+line[i].len);
		//枚举第一刀，此时cost一定是到边界的左右距离+线段长度
		printf("%.6f\n", ans);
	}
	return 0;
}