zerojudge f990. 距離

題目在 https://zerojudge.tw/ShowProblem?problemid=f990

思路是先找一個離答案夠近的點, 然後在y=mx+k這條線上去找更佳的解.

我用所有點的重心的X值,來算出線上的Y值, 這(X,Y)就當作夠近的點.

 while(j<n){
			scanf("%d %d",&xy[j][0], &xy[j][1]);
			xall+=xy[j][0];
			j++;
		}
		double x0= float(xall)/n; //所有的點的重心的x
		double y0= x0*m+k;
C++

第一步的步距delta我訂為5, 下一步位置就是(X+5, m(X+5)+k)), 如果距離的總和變大, 表示走過頭了, 就換個方向, 並減半每步的距離. 這樣來來回回的走,當步距小於0.00001程式結束.

範例的測試可以看出步距delta愈來愈小, 和換方向的過程, x也逐漸逼近0.5

程式如下

#include <stdio.h>
#include <math.h>
#include <cmath>

using namespace std;
int xy[1000000][2];

double getL(double xl, double yl) { return sqrt(xl*xl+yl*yl); }

int main(){

	int t, n, m, k;
	scanf("%d", &t);
	scanf("%d %d %d", &n, &m, &k);

	int i=0;
	int j;
	long long xall;
	while (i++<t){
		j=0;
		xall=0;
		while(j<n){
			scanf("%d %d",&xy[j][0], &xy[j][1]);
			xall+=xy[j][0];
			j++;
		}
		double x0= float(xall)/n;
		double y0= x0*m+k;
		double delta=5.0;  //第一步的步距5

		double lall=0;     //計算第一次距離和
		for(j=0;j<n;j++){
			lall+=getL(x0-xy[j][0], y0-xy[j][1]);
			}

                //開始逼近,當步距小於0.00001程式結束
		while(fabs(delta)>0.00001){
			double lpall=0;
			double xp,yp;
			for(j=0;j<n;j++){
				xp=x0+delta;
				yp=xp*m+k;
				lpall+=getL(xp-xy[j][0], yp-xy[j][1]);
				}

			if(lall < lpall){  //走過頭了, 就換個方向, 並減半每步的距離
				delta=-delta/2;
			}else{ //沒走過頭, 更新距離和
				lall=lpall;
			}
			x0+=delta;
			y0=x0*m+k;
			printf("x=%0.12f y=%f delta=%0.12f lall=%0.12f\n",x0,y0,delta,lall);
		}
		printf("%0.12f\n", x0);
	}
}
C++