[ADV 04] Point of Balance

题目的大意是X轴上有N个失重的磁力物质，这N个磁力物质的位置恒定不变。现放一个物体，在
这N个磁力物质的引力作用下会在一个平衡的位置停止下来。求这个平衡的位置坐标。
There exist n magnetic materials in a gravity-free(失重) space. The cent
er of each magnetic material is the location, i.e. the spatial coordina
te (x,y,z). Coordinates y and z of n magnetic materials are the same, a
nd only the coordinates of x are different. In other words, it is assum
ed the magnetic materials exist in a straight line. The location of the
magnetic materials is never changed by any external force. Now, when an
object is located in a random position in the straight in which n magne
tic materials exist, gravitational force acts from each magnetic materi
al. The gravitational force acting from a magnetic material on the obje
ct is obtained by the distance(d) between the magnetic material and the
object and by the masses of the magnetic material and the object.

 

Formula for calculating the gravitational force acting from a magnetic
material on the object:

F = G*m1*m2/(d*d), G is a positive constant.
                     ↓

     x ------●-----●--------○------●-------●--------●-------●----

Between the magnetic materials on the left and those on the right, the
object moves in the direction of magnetic materials with bigger force.
It is when that the two gravitational forces become the same, the objec
t stops moving. Find the point where both forces become the same. When
there are n magnetic materials, n-1 points of balance exist.

Pulling force of left magnetic materials  = Pulling force of right magnetic materials

     x ------●-----●--------○------●-------●--------●-------●----

                     ↑

                Point of balance: where both forces become the same

Note that errors of the coordinate values must be less than 10^-9(1e-9).

[Input]

A total of 10 test cases are given. For each test case, the number of m
agnetic materials N is written. In the next line, N x coordinate values,
and N mass values are input sequentially. The number(N) of magnetic mat
erials comes between 2 and 10 (2 ≤ N ≤ 10).

[Output]

For each test case, print “#C” in the first line with C being case numb
er. Leave a blank space and print out x coordinate values of the points
of balance in the same line. If the coordinate value has 10 or more dig
its after the decimal point, print only up to 10 digits.

[Input/output example] 

2          <-- test case #1 starts, number of magnetic materials

1 2 1 1    <-- Each magnetic material’s x coordinate values, and mass values (coordinate coordinate mass mass).

2          <-- test case #2 starts, number of magnetic materials

1 2 1 1000

. . .

 

Output

#1 1.5000000000

#2 1.0306534300

. . .

 
///

Real input

10                case数
2 第一个case，两个磁力物质
1 2 1 1  位置 位置 质量 质量 [注：object的质量对结果没有影响]
2
1 2 1 1000
2
457 468 333 321
3
1 2 3 1 2 1
4
2 3 5 7 3 2 7 5
5
3 11 12 19 29 542 661 450 521 366    
6
42 75 88 94 113 144 669 551 355 344 294 155
7
62 86 279 323 363 516 579 810 749 736 297 136 107 52
8
10 34 64 73 93 97 101 122 466 463 441 373 315 292 225 83
10
9 14 38 39 48 73 179 190 207 302 560 497 640 722 437 259 449 470 709 520

Real Output

#1 1.5000000000
#2 1.0306534300
#3 462.5504629633
#4 1.4060952085 2.5939047915
#5 2.5328594461 3.7271944335 6.0999536409
#6 6.3428568767 11.5477377494 15.9641592998 24.9267991615
#7 57.8805685415 81.8651598883 91.0573691382 105.0835650491 133.2934094881
#8 74.2211477711 190.6837563313 305.8269181686 348.3304429927 470.2694219293 555.4943093854
#9 21.5171374463 47.9890597763 68.6536668433 82.9131954023 95.0052272762 99.1999097770 116.4978330953
#10 11.5573600056 24.0238341337 38.4847676134 44.6137453708 64.7500445424 126.9908128982 184.3221650927 197.9760596291 266.0574653677

Code：VS2005上编译通过

#include "stdafx.h"
#include <stdio.h>
#define LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#pragma warning(disable : 4996)
#endif

#define MAX_SIZE (10)
#define PRECISION (1e-13)
#define DOUBLE_ZERO (1e-13)

double CalcForce(double x1, double x2, int m)
{
    double d = x1 > x2 ? (x1 - x2) : (x2 - x1);
    return (double)m / (d * d);
}

double FindFinePos(int x[], int m[], int N, double left, double right)
{
    double pos = (left + right) / 2.0;
    double force;
    int i;

    if (right-left < PRECISION && right-left > -PRECISION)
    {
        return pos;
    }

    force = 0.0;
    i=0;
    while(i<N){
        if (x[i] < pos)
            force += CalcForce(x[i], pos, m[i]);
        else if (x[i] > pos)
            force -= CalcForce(x[i], pos, m[i]);
        i++;
    }

    if (force > DOUBLE_ZERO)
    {
        pos = FindFinePos(x, m, N, pos, right);
    }
    else if (force < -DOUBLE_ZERO)
    {
        pos = FindFinePos(x, m, N, left, pos);
    }

    return pos;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int tc;
    int T;

    int N;
    int x[MAX_SIZE];
    int m[MAX_SIZE];
    int i;
    double pos;

#ifdef LOCAL_DEBUG
    freopen("ADV04_i.txt", "r", stdin);
    freopen("ADV04_o.txt", "w", stdout);
#endif

    setbuf(stdout, NULL);
    scanf("%d", &T);
    tc=1;
    while(tc<=T)
    {
        scanf("%d", &N);
        i=0;
        while(i<N){
            scanf("%d", &x[i]);
            i+=1;
        }
        i=0;
        while(i<N){
            scanf("%d", &m[i]);
            i++;
        }

        printf("#%d", tc);
        i=0;
        while(i<N-1){
            pos = FindFinePos(x, m, N, x[i], x[i + 1]);
            printf(" %.10f", pos);
            i++;
        }

        printf("\n");
        tc+=1;
    }

    return 0;
}

Code：VS2005上编译通过

[注]本题并不复杂，但是如果没有做过的话还真是不好处理。
for循环全部改为while循环，for循环更紧凑，但是目前我更喜欢while