[swexpert] 1245. 균형점 (c++, 이분탐색)

n개의 자성체들 사이에는 n-1개의 균형점이 무조건 존재한다고 보고 양 자성체들을 각각 s,e로 놓고

균형점(mid)의 위치를 이분탐색으로 찾아나간다.

 

오차범위가 무슨 말인지 못하다가 대략 이해했는데

만약 이분탐색으로 양쪽의 힘이 딱 같은 곳을 못발견한채로 s>e가 되어버리는 순간이 있다면 

균형점 mid를 찾아야되는데 범위를 넘어가버린다는 것은 이분탐색으로 정확히는 모르지만 s와 e사이에 균형점이 있기는 있다는 것이다. 그럼 세부 좌표 오차일 것이므로 해당 mid를 출력해버리면 된다.

 

s에 1e^12를 빼거나 e에서 뺐을 때 범위를 넘어가면 두 좌표 사이의 거리는 그것보다 작은 것이니까 그 사이에 무조건 있다. 그래도 mid를 출력해도 되는 이유는 10자리까지만 출력하기 때문인 것 같다.

 

 

#include <iostream>
#include <string>
using namespace std;

int t;

double pos[12];
double w[12];

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed;
	cout.precision(10);

	cin >> t;
	
	for (int tc = 1; tc<=t ; tc++)
	{
		
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> pos[i]; //좌표
		}
		for (int i = 0; i < n; i++) {
			cin >> w[i]; // 질량값
		}

		cout << "#" << tc << " ";
		double s = 0, e = 0;
		for (int i = 0; i < n; i++) {
			s = pos[i];
			e = pos[i + 1];

			while (s <= e) {
				double mid = (s + e) / 2;// 둘 사이 거리
				double left = 0, right = 0;
				for (int i = 0; i < n; i++) {
					double diff = mid - pos[i];
					double weight = w[i];
					if (mid > pos[i])left += (weight / (diff*diff));
					else right += (weight / (diff*diff));
				}

				if (left > right) {//왼쪽 힘이 더 셈
					s = mid + 0.000000000001;
					if (s > e) {//범위 넘어감
						cout << mid << " ";
						break;
					}
				}else if (left < right) {//오른쪽 힘이 더 셈
					e = mid - 0.000000000001;
					if (s > e) {
						cout << mid << " ";
						break;
					}
				}
				else {// 같은 곳 찾음
					cout << mid << " ";
					break;
				}

			}
		}

	cout<<"\n";

	}


	return 0;
}