思路是把平面横竖各切一刀四等分,然后以两条“划痕”的交点为原点重新建系,计算合力指向哪个象限。然后在合力指向的象限继续二分。详见代码。
#include <bits/stdc++.h>
using namespace std;
typedef long double db;
const int maxn=1004;
int n;
db minx,maxx,miny,maxy,x[maxn],y[maxn],w[maxn];
db sq(db k){ return k*k;}
db dis(db X1,db Y1,db X2,db Y2){
return sqrt(sq(X1-X2)+sq(Y1-Y2));
}
int TEST(db X,db Y){
int f=0;
db Fx=0,Fy=0;
for(int i=1;i<=n;i++){
db r=dis(X,Y,x[i],y[i]);
Fx+=w[i]*(x[i]-X)/r;
Fy+=w[i]*(y[i]-Y)/r;
}
if(Fx>=0&&Fy>=0)
f=1;
if(Fx<=0&&Fy>=0)
f=2;
if(Fx<=0&&Fy<=0)
f=3;
if(Fx>=0&&Fy<=0)
f=4;
return f;
//返回在第几象限
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%Lf %Lf %Lf",&x[i],&y[i],&w[i]);
minx=min(minx,x[i]);
maxx=max(maxx,x[i]);
miny=min(miny,y[i]);
maxy=max(maxy,y[i]);
}
db lx=minx,rx=maxx,ly=miny,ry=maxy;
while(lx+0.00001<=rx||ly+0.00001<=ry){
db px=(lx+rx)/2,py=(ly+ry)/2;
int res=TEST(px,py);
if(res==1)
lx=px,ly=py;
if(res==2)
rx=px,ly=py;
if(res==3)
rx=py,ry=py;
if(res==4)
lx=px,ry=py;
}
printf("%.3Lf %.3Lf\n",lx,ly);
return 0;
}