BZOJ 1038

传送门

先贴一发zzy的论文 Orz

姿势大概是这样:

  • 将所有半平面按极角排序
  • 多个极角相同的半平面只保留一个,就是那个限制的范围最小的
  • 维护一个栈,栈内是个凸壳或凸多边形,每次往里加边的时候剔除栈中不在限制范围内的边。若是凸壳,一个栈就够了,若是凸多边形就需要双端队列了,因为后加的边可能会覆盖最开始加的
  • 如果需要,将栈中所有边求交

拿计算几何实现的时候细节好多 = =

求两直线交点时可以直接拿叉积+定比分点公式搞,或拿解析式算 据说前一种适用范围广一点?

这道题的最优解只可能出现在凸壳的顶点或山顶,这时上下各有一个点集和一个边集,搞完凸壳以后枚举一下就能得出答案

刚开始我是枚举点集中的点和边集中的边,但是这样会出现各种奇怪的错误…因为有些边的端点并不属于点集然后blabla答案就错了 啊扯得好乱

所以只能枚举点集和另外一个点集

还有就是记得加上边界,数据中有最优解在最边上山顶的情况


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
program bzoj_1038;
const eps=1e-10;
type point=record x,y:extended; end;
line=record a,b:point; k:extended; end;
var n,m,i,tot:longint;
p,q:array[0..301]of point;
l,s:array[1..300]of line;
ans:extended;
procedure qsort(ll,rr:longint);
var i,j:longint;
mid,p:line;
begin
i:=ll;
j:=rr;
mid:=l[(ll+rr)>>1];
repeat
while l[i].k<mid.k-eps do inc(i);
while l[j].k>mid.k+eps do dec(j);
if i<=j then
begin
p:=l[i];
l[i]:=l[j];
l[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if ll<j then qsort(ll,j);
if i<rr then qsort(i,rr);
end;
procedure unique;
var i:longint;
begin
qsort(2,n);
tot:=0;
for i:=1 to n+1 do
begin
if (i=1)or(abs(l[i].k-l[i-1].k)>eps) then inc(tot);
l[tot]:=l[i];
end;
end;
function convt(a,b:point):line;
begin
convt.a:=a;
convt.b:=b;
end;
function cross(l1,l2:line):extended;
begin
exit((l1.b.x-l1.a.x)*(l2.b.y-l2.a.y)-(l1.b.y-l1.a.y)*(l2.b.x-l2.a.x));
end;
function inter(l1,l2:line):point;
var s1,s2,t:extended;
begin
s1:=cross(l1,convt(l1.a,l2.a))/2;
s2:=cross(convt(l1.a,l2.b),l1)/2;
t:=s1/(s1+s2+eps);
inter.x:=l2.a.x+t*(l2.b.x-l2.a.x);
inter.y:=l2.a.y+t*(l2.b.y-l2.a.y);
end;
function upper(p:point;l:line):boolean;
begin
exit(cross(l,convt(l.a,p))+eps>0);
end;
procedure solve;
var top,i,j:longint;
t:point;
h:extended;
begin
s[1]:=l[1];
s[2]:=l[2];
top:=2;
for i:=3 to tot do
begin
while (top>1)and(not upper(inter(s[top-1],s[top]),l[i])) do dec(top);
inc(top);
s[top]:=l[i];
end;
m:=top-1;
for i:=1 to m do q[i]:=inter(s[i],s[i+1]);
ans:=maxlongint<<32;
t.y:=0;
for i:=1 to m do
for j:=1 to n-1 do if (p[j].x<=q[i].x)and(p[j+1].x>=q[i].x) then
begin
t.x:=q[i].x;
h:=q[i].y-inter(convt(q[i],t),convt(p[j],p[j+1])).y+eps;
if h<ans then ans:=h;
end;
for i:=1 to n do
for j:=1 to m-1 do if (q[j].x<=p[i].x)and(q[j+1].x>=p[i].x) then
begin
t.x:=p[i].x;
h:=inter(convt(p[i],t),convt(q[j],q[j+1])).y-p[i].y+eps;
if h<ans then ans:=h;
end;
end;
begin
readln(n);
for i:=1 to n do read(p[i].x);
for i:=1 to n do read(p[i].y);
p[0].x:=p[1].x;
p[0].y:=100000;
p[n+1].x:=p[n].x;
p[n+1].y:=1000000;
for i:=1 to n+1 do
begin
l[i].a:=p[i-1];
l[i].b:=p[i];
l[i].k:=arctan((p[i-1].y-p[i].y)/(p[i-1].x-p[i].x+eps));
end;
unique;
solve;
writeln(ans:0:3);
end.