[SWEA] 균형점

처음에는 방정식을 푸는 문제인 줄 알았지만 식을 좀 써보니 계산용이 아니라 그냥 오차범위 내의 값을 찾는 것 같았다

parametric search를 이용해 풀어야겠다는 생각이 들었다

이 때 범위를 구해주어야 하는데 뭔가 각 점들의 사이이지 않을까 하는 생각이 들어서 input을 까봤다

SW 아카데미는 인풋, 아웃풋을 많이 알려줘서 좋다ㅎㅎ..

안좋은 습관 고쳐야하는데...

아무튼!! input, output을 까봤더니 정말 각 점들의 사이가 답이었다

이유는 조금 더 생각해봐야 할 것 같다

 

각 점들의 사이를 범위로 주고 parametric search를 통해 오차범위 내의 답을 구해보았다

모든 자성체에서 동일한 G와 균형점의 무게가 될 m1은 무시했다

코드에 문제가 없어 보였지만 왜인지 모르게 segmentation fault가 떴다

프린트로 원인을 찾아보니 double 변수형 제한에 걸려 mid 값이 바뀌지 않고 재귀함수를 계속 호출하는 것을 알 수 있었다

parametric search 함수에 이전 mid값을 before로 넘겨 안바뀐다면 한계에 도달한 것으로 파악하고 함수를 종료시켜주었더니 해결되었다

 

parametric search 문제 잘 못푸는 편이었는데 이번 기회에 풀어봐서 좋았다

 

#include <stdio.h>
 
int positions[15];
int weights[15];
 
double get_force(int idx, double x){
    double dist = x-positions[idx];
    if(dist==0) return 0;
    return weights[idx] / (dist*dist);
}
 
double abs(double x){
    return x>=0?x:-x;
}
 
double parametric_search(double left, double right,int N,int idx, double before){
    double mid = ((double)left + (double)right) / 2;
    double left_force = 0.0,right_force = 0.0;
    
    for(int i = 0 ; i <= idx ; i++) left_force += get_force(i,mid);
    for(int i = idx+1 ; i < N ; i++) right_force += get_force(i,mid);
    if(before==mid) return mid;
    if (abs(left_force-right_force) >= 0.0000000000001)
    {
        if (left_force > right_force) return parametric_search(mid,right,N,idx,mid);
        else return parametric_search(left,mid,N,idx,mid);
    }
    return mid;
}
 
int main(){
    int T;
    scanf("%d",&T);
    for(int test_case = 1 ; test_case <= T ; test_case++){
        int N;
        scanf("%d",&N);
        for(register unsigned int i = 0 ; i < N ; i++) scanf("%d",&positions[i]);
        for(register unsigned int i = 0 ; i < N ; i++) scanf("%d",&weights[i]);
 
        printf("#%d ",test_case);
        for(int i = 0; i < N-1 ; i++){
            int left = positions[i], right = positions[i+1];
            printf("%.10lf ",parametric_search(left,right,N,i,-1));
        }
        printf("\n");
    }
}