URAL-1894-Non-Flying-Weather

题意:给你两个相交的凸包,其中一个可以任意移动,问最少多久能使两个凸包分离
前置技能点:闽科夫斯基和:设P和Q是两个凸包,则有闽科夫斯基和 P+Q={a+b|a∈P,b∈Q} ,闽科夫斯基差 P-Q={a-b|a∈P,b∈Q}

性质:P+Q是一个凸包,同时也是P和Q的所有并踵点对的和的集合,P+Q顶点数不超过P和Q的顶点和
其差P-Q是一个凸包,同时也是P和Q的所有对踵点对的差的集合,P-Q顶点数不超过P和Q的顶点和,若P和Q相交,则P-Q包含原点
那么,本题就是求一个闽科夫斯基差的凸包,找出原点到凸包的最短距离……所以可以用旋转卡壳跑出所有对踵点对,然后求一下点-边的对踵点对中点到直线的距离就好了

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
//created by missever
#include<bits/stdc++.h>
#define MAX 1000000007
using namespace std;
typedef long long LL;
const double eps = 1e-10;
const double pi = acos(-1);
const int maxn = 5e4 + 5;
inline int sgn(double x) {
if(x < -eps) return -1;
else if(x > eps) return 1;
else return 0;
}
struct Point {
double x,y;
Point(double _x = 0.0,double _y = 0.0): x(_x),y(_y) {}
Point operator + (const Point &b) const {
return Point(x + b.x,y + b.y);
}
Point operator - (const Point &b) const {
return Point(x - b.x,y - b.y);
}
double operator * (const Point &b) const { //点乘
return (x * b.x + y * b.y);
}
double operator ^ (const Point &b) const { //叉乘,判断b点的相对于该点位置关系 左正右负
return (x * b.y - y * b.x);
}
Point operator * (double b) {
return Point(x * b,y * b);
}
double norm() { //求模
return sqrt(x * x + y * y);
}
};
struct Line {
Point s,e;
Line() {}
Line(Point _s,Point _e) {
s = _s;
e = _e;
}
};
double dist(Point &a,Point &b) {
return (a - b).norm();
}
Point Point_to_Line(Point p,Line l)
{
double t = ((p - l.s) * (l.e - l.s)) / ((l.e - l.s) * (l.e - l.s));
return Point(l.s.x + (l.e.x - l.s.x) * t,l.s.y + (l.e.y - l.s.y) * t);
}
//旋转卡壳
double rot_solve(Point a[],Point b[],int n,int m) {
int fa,fb,i;
Point u;
for(fa = i = 0; i < n; i++) {
if(a[i].y < a[fa].y) fa = i;
}
for(fb = i = 0; i < m; i++) {
if(b[i].y > b[fb].y) fb = i;
}
a[n] = a[0];
b[m] = b[0];
double ans = 1e18;
for(i = 0; i < n; i++) {
while(sgn(((a[fa + 1] - a[fa]) ^ (b[fb + 1] - a[fa]))- ((a[fa + 1] - a[fa]) ^ (b[fb] - a[fa]))) == 1) fb = (fb + 1) % m;
u = Point_to_Line(b[fb],Line(a[fa],a[fa + 1]));
ans = min(ans,(b[fb] - u).norm());
fa = (fa + 1) % n;
}
return ans;
}
Point a[maxn],b[maxn];
int main() {
int n,m,i;
double x,y;
scanf("%d%d",&n,&m);
for(i = 0; i < n; i++) {
scanf("%lf%lf",&x,&y);
a[i] = Point(x,y);
}
for(i = 0; i < m; i++) {
scanf("%lf%lf",&x,&y);
b[i] = Point(x,y);
}
double ans = min(rot_solve(a,b,n,m),rot_solve(b,a,m,n));
ans -= 60.0;
if(sgn(ans) <= 0) printf("0\n");
else printf("%.12f\n",ans);
return 0;
}