FJWC2016 BZOJ2517 有没有wifi【分治】
一家餐馆可以视为一个 L×W 的矩形，其安装了 N 个无线路由器，每个无线
路由器给定坐标 x[i],y[i]以及覆盖半径 R[i]（可以安装在餐馆外部） 。老板邀
请了一位神奇程序员来调整无线路由器的发射倍率， 可以将所有路由器的覆盖半
径乘以一个系数 K，求最小的 K 使得无线覆盖整个餐馆的同时又最节省成本。
这道题我们采用暴力分治。
对于一个矩形，如果四个顶点都被同一个圆包含，那么肯定答案为true；如果有一个顶点没有被任何圆包含，则答案为false。其他情况，就把矩形切成四份，继续下去。
时间复杂度$O(Tlog_{2}^{2}L)$。
# include <stdio.h>
using namespace std;
int T,W,L,n;
struct circle {
double x,y,r;
}p[110],t[110];
const double eps=1e-6,meps=-eps;
inline double sqr(double x) {
return x*x;
}
//point in circle(or on)
inline bool pinc(double x,double y,double cx,double cy,double cr) {
return sqr(x-cx)+sqr(y-cy)<sqr(cr);
}
//(x,y) --> (xx,yy)
inline bool chk(double x,double y,double xx,double yy) {
if(xx-x<eps&&yy-y<eps) return 1;
bool aa1,aa2,aa3,aa4;
aa1=aa2=aa3=aa4=0;
for (int i=1;i<=n;++i) {
bool a1,a2,a3,a4;
a1=pinc(x,y,t[i].x,t[i].y,t[i].r);
a2=pinc(xx,yy,t[i].x,t[i].y,t[i].r);
a3=pinc(x,yy,t[i].x,t[i].y,t[i].r);
a4=pinc(xx,y,t[i].x,t[i].y,t[i].r);
aa1|=a1,aa2|=a2,aa3|=a3,aa4|=a4;
if(a1&&a2&&a3&&a4) return 1;
}
double mix=(x+xx)/2,miy=(y+yy)/2;
if(!aa1 || !aa2 || !aa3 || !aa4) return 0;
else return chk(x,y,mix,miy)&&chk(x,miy,mix,yy)&&chk(mix,y,xx,miy)&&chk(mix,miy,xx,yy);
}
inline bool check(double k) {
for (int i=1;i<=n;++i) {
t[i].x=p[i].x;
t[i].y=p[i].y;
t[i].r=p[i].r*k;
}
return chk(0.0,0.0,(double)W,(double)L);
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&W,&L);
for (int i=1;i<=n;++i)
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
double le=0.0,ri=1000.0,mi;
while(ri-le>eps) {
mi=(le+ri)/2.0;
if(check(mi)) ri=mi;
else le=mi;
}
printf("%.3lf\n",le);
}
return 0;
}
2023年4月24日 18:46
The Wi-Fi routers have IPv4 private network IP address or default gateway such as Tenda, Cisco Linksys, Netgear, TP-Link, D-Link, Asus, Apple AirPort Extreme, Private IPv4 network address is 192.168.1.1 or 10.0.0.1. to ip-192-168-0-1.com config the WiFi routers enter the default IP address 192.168.1.1 (192.168.o.1) on your web browser where create the home or small office user ID passwords and manage router’s settings, the leading router manufacturers of D-Link or Netgear brands made the IP 192.168.0.1 next to IP 192.168.1.1 and IP 192.168.2.1.