1245. 균형점

자성체 N개가 주어질 때 자성체 사이사이의 균형점을 구해서 출력하는 문제다.

F = G*m1*m2/(d*d)라고 되어있는데 아무곳에서 자성체 하나를 놓고 계산을 해보면

G와 물체의 질량은 계산식에 전혀 영향을 미치지 못하는 것을 알 수 있다.

이 문제에서는 이분탐색을 사용할 것이다.

현재 균형점이라 생각할 지점에서 왼쪽 자성체들에게 받는 힘을 더하고

오른쪽 자성체들에게 받는 힘을 뺐을 때 0이 된다면 그곳은 균형점일 것이다.

하지만 소수점 계산이라 정확한 0이 나오기는 힘들고 입력값의 범위도 주어져 있지 않으므로 그냥 int범위로 생각하고 풀자.

int가 대충 1e9정도이므로 이것을 토대로 계산했을 때 오차가 1e-9 미만이어야 한다는 것은 계산 범위가 1e18과 같다는 것이므로

루프를 60번은 돌아야 한다.(50번 돌아도 통과하더라. 간혹 input의 범위가 불분명한 문제가 있어 난감하다)

i번째 자성체의 위치를 l로잡고 i+1번째를 r로 잡은 후 그 사이에서 이분탐색을 한다.

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef double db;
 
int t, n;
db x[10], m[10];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cout << fixed;
    cout.precision(10);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> x[i];
        for (int i = 0; i < n; ++i) 
            cin >> m[i];
        cout << "#" << tc << " ";
        for (int i = 0; i < n - 1; ++i) {
            db l = x[i], r = x[i + 1], ans = 0;
            for (int k = 0; k < 50; ++k) {
                db mid = (l + r) / 2;
                db s = 0;
                for (int j = 0; j <= i; ++j) 
                    s += m[j] / ((mid - x[j])*(mid - x[j]));
                for (int j = i + 1; j < n; ++j) 
                    s -= m[j] / ((mid - x[j])*(mid - x[j]));
                if (s > 0) {
                    l = mid;
                }
                else {
                    ans = mid;
                    r = mid;
                }
            }
            cout << ans << " ";
        }
        cout << '\n';
        //cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}