[Bài toán] Tìm điểm căn bằng.

Ở một dải ngân hà X có n hành tinh. Tọa độ của mỗi hành tinh được đặc trưng bởi 3 tọa độ (x,y,z). Vào một thời điểm nào đó trong năm, các hành tinh được sắp xếp trên một đường thẳng x (y = z = 0). Đây là một hiện tượng khoa học thú vị, các nhà khoa học đã đặt ra  câu hỏi: Ở những vị trí nào trên đường thẳng x khi đặt một hành tinh M vào đó thì hành tinh đó dứng yên.

Được biết rằng giữa hai hành tinh luôn tồn tại lực hấp dẫn. Lực này được tính theo công thức : F = G *m1*m2/(d*d).

• Trong đó : G là hằng số vũ trụ.
• m1, m2 lần lượt là khối lượng của hai hành tinh. 
• d là khoảng cách giữa  chúng.

Hãy làm tròn vị trí tìm được đến 1/10^9.
*Note: Biết rằng khi có n hành tinh thì ta luôn tìm được n-1 vị trí cân bằng cho hành tinh M.
[Input]
Dữ liệu của 10 test case được chứa trong file POINTOFBALANCE.INP. Dòng đầu ghi số hành tinh N của dải ngân hà X.
Dòng sau ghi tọa độ của N hành tinh trên trục x, theo ngay sau là khối lượng của N hành tinh.
[Output]
Hãy ghi ra file POINTOFBALANCE.OUT tất cả các điểm cân bằng trên trục x. Mỗi test case được bắt đầu bằng #C và các vị trí được ngăn cách với nhau bởi dấu cách.

[I/O example]
2  :// số hành tinh của dải ngân hà.
1 2 1 1 :// vị trí của 2 hành tinh [1 2] và khối lượng của 2 hành tinh [1 1].
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
[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

[Giải thuật]

1. Với n ( H1,H2,H3,H3,...Hn) hành tinh thì có n - 1 vị trí căn bằng. Các vị trí này nằm ở khoảng giữa giữa 2 hành tinh (Xk, Xk+1). (1 <= k <=n-1)
2. Trong khoảng (Xk, Xk+1) ta lấy điểm chính giữa (điểm P1) và tính lực tác động của tất cả các hành tinh bên trái M và bên phải M lên hành tinh M. Nếu lực hút của các hành tinh bên trái lớn hơn bên phải thì điểm cân bằng sẽ nằm bên phải của điểm P1. Nếu lực hút của các hành tinh nằm bên phải lớn hơn bên trái thì điểm cân bằng sẽ nằm bên trái điểm P1.
3. Giả sử lực hút của các hành tinh nằm bên trái M lớn hơn bên phải thì điểm cân bằng sẽ nằm bên phải P1. Giờ xét điểm P2 nằm giữa P1 và Xk+1 và lặp lại bước 2. Cứ tiếp tục chia nhỏ như vậy cho đến khi khoảng cách của đoạn thẳng đủ nhỏ ( <= 1/10^9).
4. Ta được điểm Pn là điểm cần tìm.

Chương trình cài đặt.

 
#include<iostream>
#include<stdio.h>
using namespace std;
int n;
#define nMax 11
int material[nMax][2];
int main(){
 freopen("POINTOFBALANCE.INP","r", stdin);
 freopen("POINTOFBALANCE.OUT","w", stdout);
 for(int tc=1;tc<=10;tc++){
  cin>>n;
  for(int j=1;j<=n;j++){
   cin>>material[j][0];
  }
  for(int j=1;j<=n;j++){
   cin>>material[j][1];
  }
  cout<<"#"<<tc<<" ";
  double gravitationalLeft, gravitationalRight;
  for(int k=1;k<n;k++){
   double leftPoint = material[k][0];
   double rightPoint = material[k+1][0];
   double middle = rightPoint;
   while(rightPoint - leftPoint > 0.000000000001){
    middle = (rightPoint - leftPoint)/2 + leftPoint;
    gravitationalLeft = gravitationalRight =0;
    for(int i=1;i<n && material[i][0]<middle;i++){
     gravitationalLeft+=material[i][1]/((material[i][0] - middle) * (material[i][0] - middle));
    }
    for(int j=n;j>1 && material[j][0] > middle; j--){
     gravitationalRight+=material[j][1]/((material[j][0] - middle) * (material[j][0] - middle));
    }
    if(gravitationalLeft < gravitationalRight) rightPoint = middle;
    else if(gravitationalLeft > gravitationalRight)  leftPoint = middle;
    else { break;}
   }
   printf("%.10lf ",middle);
  }
  cout<<endl;

 }
 return 0;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.