[SWEA 1245] 균형점

문제출처는 링크를 걸어도 따로 로그인해야 하기 때문에 적지 않겠습니다.

이진탐색 이용

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
struct coordinates {
    int x;
    int y;
};
 
 
coordinates map[11];
 
// 인력 F = G*m1*m2 / (d*d)
// G = 양의 상수
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed;
    cout.precision(10);
    int tc, n;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> map[i].x;
        for (int i = 1; i <= n; i++)
            cin >> map[i].y;
 
        cout << "#" << t << " ";
        for (int i = 1; i < n; i++) {
            double x;
            double left = map[i].x;
            double right = map[i + 1].x;
 
            int cnt = 0;
            while (true) {
                x = (left + right) / 2.0;
                double lf = 0;
                double rf = 0;
                for (int j = 1; j <= i; j++)
                    lf += (map[j].y) / ((map[j].x - x) * (map[j].x - x));
                for(int j=i+1; j<=n; j++)
                    rf += (map[j].y) / ((map[j].x - x) * (map[j].x - x));
 
                if (cnt++ == 100) {
                    cout << x << " ";
                    break;
                }
 
                if (lf > rf)
                    left = x;
                else
                    right = x;
            }
        }
        cout << endl;
    }
    return 0;
}

다른 풀이도 공개해서 보니 이런 풀이도 있었다.

#include<stdio.h>
#define E 1e-9
int n, m;
int a[99];
int b[99];
bool less(double x) {
    int i, j, k;
    double sum = 0;
    double cur;
    for (i = 0; i < m; i++) {
        cur = (x - a[i]);
        cur *= cur;
        if (cur < E) return false;
        cur = b[i] / cur;
        sum += cur;
    }
    for (i = m; i < n; i++) {
        cur = (x - a[i]);
        cur *= cur;
        if (cur < E) return true;
        cur = b[i] / cur;
        sum -= cur;
    }
    return sum < 0;
}
 
int main() {
    int t, tv = 0;
    int i, j, k, l;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 0; i < n; i++)scanf("%d", &a[i]);
        for (i = 0; i < n; i++)scanf("%d", &b[i]);
        printf("#%d", ++tv);
        for (m = 1; m < n; m++) {
            double l, r, mid;
            l = a[m - 1];
            r = a[m];
            int cnt = 100;
            while (cnt--) {
                mid = (l + r) / 2;
                if (less(mid))
                    r = mid;
                else
                    l = mid;
            }
            printf(" %.10lf", l);
        }
        printf("\n");
    }
}