我的思路很暴力

直接枚舉斜率[-100000,0]之間，然后設置一個非常遠的直線，對所有點掃一遍，確定一個離這條直線最近的點P。

用點P和斜率k來創建cable，并用cable的距離來relax答案。

現在問題在于，怎么來枚舉k，如果直接枚舉，設置步長的話，不是超時就是精度不足。

因此我們需要想個辦法來枚舉k。

我們先枚舉0,10000,20000,...,100000找到一個最優答案，假設是20000

那么我們再枚舉21000,22000.....,29000以及19000,18000,...11000這些數，找到一個最優的，這樣一直找下去，總會找到k。

枚舉的時間復雜度為O(10*迭代深度)

具體原理看我下一篇文章。

這道題目卡精度，注意了

代碼：

#include <cstdio> #include <cmath> using namespace std;const int maxn = 1e6+7; const double INF = 1e18; struct Point{ int x,y; }Ps[maxn];? int n; int check(double k){ double t = INF; int mark = 0; for(int i = 0;i < n;++i){ if(abs(k*Ps[i].x-Ps[i].y+(1-k)*10000) < t){ t = abs(k*Ps[i].x-Ps[i].y+(1-k)*10000); mark = i; } } return mark; } double getans(double k,int id){ double a = -k*Ps[id].x + Ps[id].y; double b = -Ps[id].y/k+Ps[id].x; return a*a+b*b; } double f(double k){ int id = check(-k); double ans = getans(-k,id); return ans; } double csf(double l,double r,int n = 6,double eps = 0.0000001){??double x;while(r - l > eps){double step = (r-l)/(n+1);double mx = INF;for(double i = l+step;i < r;i += step) { double t = f(i); if(mx > t){mx = t; x = i; } }l = x-step;r = x+step;}return l; }? int main(){ while(scanf("%d",&n)!=EOF){ for(int i = 0;i < n;++i){ scanf("%d %d",&Ps[i].x,&Ps[i].y); } double k = csf(0,10000,4); printf("%.3lf\n",sqrt(f(k))); } return 0;? }?

總結

以上是生活随笔為你收集整理的codeforces Cable Connection的全部內容，希望文章能夠幫你解決所遇到的問題。

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