|
题目大意：平面上有一个$N \times M$的矩形，矩形内有K个点，现给出每个点的坐标，找一条从左边界到右边界的路径，使路径到矩形上下边界及矩形内点的最小距离最大。 20%：$(K<=10)$ 直接暴搜。 50%：$(K<=400)$ 我们以点为圆心画圆。 那么存在一条路径的条件是这些圆没有将半径封死。 我们可以二分圆的半径，每次将相交的圆合并，将上下边界视作点，查询上下边界是否在同一集合内部，若在，则判定失败。 时间复杂度$O(K^2*log_2ANS)$ 100%：$(K<=6000)$ 我们发现二分答案占有相当复杂度，于是我们考虑去掉。 我们把所有点连同上下边界连在一张图里，发现起到限制作用的只用上下边界之间的通路。 答案即为最大值最小的通路上边权的最大值。 做一遍最小生成树，DFS求出上下边界之间的通路上的最大边权。 由于是完全图，我们只能用Prim，并且为了减少内存，边权要现算。 时间复杂度$O(K^2)$ Code： 
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<cmath>
5 #include<vector>
6 using namespace std;
7 const int N=6003;
8 int n,m,k,U,D;
9 int fi[N],f[N];
10 long long a[N],b[N];
11 double d[N];
12 bool v[N];
13 vector<int> e[N];
14 vector<double> l[N];
15 void add(int x,int y,double z)
16 {
17 e[x].push_back(y);
18 l[x].push_back(z);
19 }
20 double get(int x,int y)
21 {
22 if((x==D&&y==U)||(x==U&&y==D)) return m;
23 if(x==D) return b[y];
24 if(y==D) return b[x];
25 if(x==U) return m-b[y];
26 if(y==U) return m-b[x];
27 double ans=(a[x]-a[y])*(a[x]-a[y]) (b[x]-b[y])*(b[x]-b[y]);
28 return sqrt(ans);
29 }
30 void dfs(int x,int p)
31 {
32 for(int i=0;i<e[x].size();i ){
33 int y=e[x][i];
34 if(y==p) continue;
35 d[y]=max(d[x],l[x][i]);
36 dfs(y,x);
37 }
38 }
39 void Prim()
40 {
41 for(int i=1;i<=k 2;i )
42 d[i]=99999999;
43 d[1]=0;
44 for(int i=1;i<=k 1;i ){
45 int x=0;
46 for(int j=1;j<=k 2;j ){
47 if(!v[j]&&(x==0||d[j]<d[x])) x=j;
48 }
49 v[x]=true;
50 for(int j=1;j<=k 2;j ){
51 double y=get(x,j);
52 if(!v[j]&&y<d[j]){
53 d[j]=y;f[j]=x;
54 }
55 }
56 }
57 }
58 int main()
59 {
60 scanf("%d%d%d",&n,&m,&k);
61 U=k 1;D=k 2;
62 for(int i=1;i<=k;i )
63 scanf("%lld%lld",&a[i],&b[i]);
64 Prim();
65 for(int i=2;i<=k 2;i ){
66 add(i,f[i],d[i]);add(f[i],i,d[i]);
67 d[i]=0;
68 }
69 dfs(U,0);
70 printf("%.8lf\n",d[D]/2.0);
71 return 0;
72 }
view code
来源：https://www./content-4-401101.html
|
|
|
