BZOJ

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.