这个题直接用二分法把平面四等分的做法有什么问题吗?
查看原帖
这个题直接用二分法把平面四等分的做法有什么问题吗?
361965
K2Cr2O7楼主2023/2/1 15:25

思路是把平面横竖各切一刀四等分,然后以两条“划痕”的交点为原点重新建系,计算合力指向哪个象限。然后在合力指向的象限继续二分。详见代码。

#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;
}
2023/2/1 15:25
加载中...