[1245번] 균형점

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분탐색

이분탐색을 이용하여 균형점을 찾아 낼 수 있다. 

각 점 사이에 균형점이 있다 가정하고 이분탐색을 통해 

균형점을 찾아 인력을 계산해주어 답을 찾아낸다.

소스 코드 : 

#include <iostream>
 
typedef double db;
db pos[12];
db weight[12];
 
int main() {
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        int n;
        scanf("%d", &n);
        db s = 0, e = 0.0;
        for (int i = 0; i < n; i++)
            scanf("%lf", &pos[i]);
        for (int i = 0; i < n; i++)
            scanf("%lf", &weight[i]);
 
        printf("#%d ", tc);
 
        for (int i = 0; i < n; i++) {
            s = pos[i], e = pos[i + 1];
 
            bool chk = false;
            db mid = (s + e) / 2;
            while (s <= e) {
                db mid = (s + e) / 2;
 
                db left = 0.0, right = 0.0;
                for (int i = 0; i < n; i++) {
                    db d = mid - (db)pos[i];
                    db m = weight[i];
                    if ((db)pos[i] < mid)
                        left += (m / (d * d));
                    
                    else if ((db)pos[i] > mid)
                        right += (m / (d * d));
                }
 
                if (left > right) {
                    s = mid + 0.000000000001;
                    if (s > e) {
                        printf("%.10lf ", mid);
                        chk = true;
                        break;
                    }
                }
                else if (left < right)
                {
                    e = mid - 0.000000000001;
                    if (s > e) {
                        printf("%.10lf ", mid);
                        chk = true;
                        break;
                    }
                }
                else {
                    printf("%.10lf ", mid);
                    chk = true;
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}