「BZOJ3822」文学 - 区间动规+计算几何 | Bill Yang's Blog

「BZOJ3822」文学 - 区间动规+计算几何

题目大意

    有若干个半平面,要求选出一些半平面,使得这些半平面的并包含所有点,且选出的半平面权值最小。


题目分析

首先我们要找到一个基点,然后通过基点按照某种顺序处理半平面。
不妨枚举两个半平面,得到它们的交点,以这个交点作为基点。
此时,我们只需要考虑这两个半平面没有覆盖的范围(如图,没有被蓝色覆盖的范围)。

对剩下的点极角排序,转化为区间问题,计算出每个半平面能够覆盖的区间范围。
对半平面作个区间动规求出$g(i,j)$表示用一个半平面能够覆盖$i\sim j$的最小权值。
$f(i)$表示覆盖$1\sim i$所有点的最小权值。

区间动规的正确性可以用凸包上的半平面证明。

总时间复杂度$O(n^4)$。


代码

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
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=105;
struct Line {
double a,b,c;
int v;
} L[maxn];
struct Point {
double x,y;
Point(double x=0,double y=0):x(x),y(y) {}
Point operator - (const Point &a) const {return Point(x-a.x,y-a.y);}
} p[maxn],vec[maxn],p0;
typedef Point Vector;
double Cross(Vector a,Vector b) {return a.x*b.y-a.y*b.x;}
bool operator < (const Point &a,const Point &b) {return Cross(a-p0,b-p0)<0;}
bool Inplane(Line l,Point p) {return l.a*p.x+l.b*p.y<=l.c;}
Point Intersection(Line x,Line y) {
x.c*=-1,y.c*=-1;
double down=x.b*y.a-y.b*x.a;
return Point((x.c*y.b-y.c*x.b)/down,(x.c*y.a-y.c*x.a)/-down);
}
int n,m,ans=0x3f3f3f3f,f[maxn],g[maxn][maxn];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)scanf("%lf%lf%lf%d",&L[i].a,&L[i].b,&L[i].c,&L[i].v);
for(int i=1; i<=m; i++)scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=1; i<=n; i++) {
bool bj=1;
for(int j=1; j<=m; j++)if(!Inplane(L[i],p[j])) {bj=0;break;}
if(bj)ans=min(ans,L[i].v);
}
for(int i=1; i<=n; i++)
for(int j=1; j<i; j++) {
p0=Intersection(L[i],L[j]);
int tot=0;
for(int k=1; k<=m; k++)if(!Inplane(L[i],p[k])&&!Inplane(L[j],p[k]))vec[++tot]=p[k];
sort(vec+1,vec+tot+1);
memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g));
for(int k=1; k<=n; k++)if(k!=i&&k!=j)
for(int l=1; l<=tot; l++) {
if(!Inplane(L[k],vec[l]))continue;
int r=l;
while(r<tot&&Inplane(L[k],vec[r+1]))r++;
g[l][r]=min(g[l][r],L[k].v);
l=r+1;
}
for(int len=tot; len>=2; len--)
for(int l=1; l+len-1<=tot; l++) {
int r=l+len-1;
g[l+1][r]=min(g[l+1][r],g[l][r]);
g[l][r-1]=min(g[l][r-1],g[l][r]);
}
f[0]=0;
for(int r=1; r<=tot; r++)
for(int l=0; l<r; l++)
f[r]=min(f[r],f[l]+g[l+1][r]);
ans=min(ans,f[tot]+L[i].v+L[j].v);
}
printf("%d\n",ans>=0x3f3f3f3f?-1:ans);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%