天津网站排名方案,四川游戏seo整站优化,免费php源码资源网,网站建设开发网站案例项目费用我的思路很暴力
直接枚举斜率[-100000,0]之间#xff0c;然后设置一个非常远的直线#xff0c;对所有点扫一遍#xff0c;确定一个离这条直线最近的点P。
用点P和斜率k来创建cable#xff0c;并用cable的距离来relax答案。
现在问题在于#xff0c;怎么来枚举k#xf…我的思路很暴力
直接枚举斜率[-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 1e67;
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/kPs[id].x;
return a*ab*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)/(n1);
double mx INF;
for(double i lstep;i r;i step) {
double t f(i);
if(mx t){
mx t;
x i;
}
}
l x-step;
r xstep;
}
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;
}
