現在時間太少了，只能把自己不會的題補一下，會的題就不寫了

F - Silver Woods

顯然可以二分圓的半徑，那么現在問題轉化成判斷半徑為$r$的圓是否能夠滿足題意。

考慮什么情況下該半徑的圓不能通過這些點。嘗試用并查集維護一些關系

如果兩個點之間的距離$<2r$那么說明該圓不能從兩者之間通過，那么我們在他們兩點之間連一條邊。
最后維護完并查集不難發現該圓不能完全通過連通塊內的點。
如果該題只能從兩點之間通過，那么想要滿足題意上述連通塊的個數必須$=n$

不過該題可以讓邊界和點之間通過，那么嘗試加入兩個“點”，考慮每個點與上下邊界的關系，如果距離小于 $2r$ 一樣不能通過，那么我們在他們之間連邊。

最后如果加入的兩個“點”如果不在一個連通塊內，那么說明一定有路徑滿足題意，如果在一個連通塊內，說明不存在路徑。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=110; int n; pii a[N]; double dist(int u,int v) {int dx=a[u].first-a[v].first;int dy=a[u].second-a[v].second;return sqrt(double(dx*dx+dy*dy)); } int p[N]; int find(int x) {return x==p[x]?x:p[x]=find(p[x]);} bool check(double r) {int s=0,t=n+1;for(int i=s;i<=t;i++) p[i]=i;for(int i=1;i<=n;i++){if(100-a[i].second<2*r) p[find(i)]=find(s);if(a[i].second+100<2*r) p[find(i)]=find(t);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(dist(i,j)<2.0*r)p[find(i)]=find(j);return find(s)==find(t); } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;double l=0,r=100.0;while(r-l>1e-6){double mid=(l+r)/2;if(check(mid)) r=mid;else l=mid;}printf("%.6lf",l);}return 0; }

天天就會打模板？學那么多數據結構有什么用，可能還是見的題太少了，要加油哦~

總結

以上是生活随笔為你收集整理的ABC181——F - Silver Woods的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。