Pointofbalance

Level 4
Point of Balance 2
There exist n magnetic materials in a gravity-free space. The center of each magnetic material is the location, i.e., the spatial coordinate (x,y,z). Coordinates y and z of n magnetic materials are the same, and only the coordinates of x are different. In other words, it is assumed 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 magnetic materials exist, gravitational force acts from each magnetic material. The gravitational force acting from a magnetic material on the object 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.

 

 

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 object stops moving. Find the point where both forces become the same. When there are n magnetic materials, n-1 points of balance exist.

 


Point of balance: where both forces become the same: Pulling force of left magnetic materials = Pulling force of right magnetic materials

 

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 magnetic materials N is written. In the next line, N x coordinate values, and N mass values are input sequentially. The number (N) of magnetic materials comes between 2 and 10 (2 ≤ N ≤ 10).

 

 

[Output]

For each test case, print “#C” in the first line with C being case number. 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 digits after the decimal point, print only up to10 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

. . .


#1 1.5000000000
#2 1.0306534300
#3 462.5504629633
#4 1.4060952085 2.5939047915
#5 2.5328594461 3.7271944336 6.0999536408
#6 6.3428568767 11.5477377494 15.9641592998 24.9267991615
#7 57.8805685414 81.8651598883 91.0573691382 105.0835650496 133.2934094854
#8 74.2211477715 190.6837562509 305.8269181671 348.3304429911 470.2694221549 555.4943093844
#9 21.5171374455 47.9890597761 68.6536668433 82.9131954019 95.0052272762 99.1999097770 116.4978330954
#10 11.5573600056 24.0238341335 38.4847676134 44.6137453708 64.7500445430 126.9908129163 184.3221650927 197.9760596292 266.0574653796

 2
1 2 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
#include <iostream>
using namespace std;

int T, n, k;
int arr[11][2];
double L[11], R[11], result[11];

double calcLeft(int l, double value){
	double ans = 0.0;
	for(int i = l; i > 0; i--){
		ans += (1.0*arr[i][1]/(value - 1.0*arr[i][0])/(value - 1.0*arr[i][0]));
	}
	return ans;
}

double calcRight(int r, double value){
	double ans = 0.0;
	for(int i = r+1; i <= n; i++){
		ans += (1.0*arr[i][1]/(arr[i][0]*1.0 - value)/(arr[i][0]*1.0 - value));
	}
	return ans;
}

void binarySearch(double l, double r, int index){
	double m = (l+r) /2.0;
	while(l < r){
		double s1 = calcLeft(index, m);
		double s2 = calcRight(index, m);
		if((s1 > s2 && s1 - s2 < 1e-9) || (s2 > s1 && s2 - s1 < 1e-9) || s1 == s2){
			if(m > l && m < r)result[k++] = m;
			break;
		} else if(s1 > s2){
			l = m, m = (l+r)/2.0;
		} else {
			r = m, m = (r+l)/2.0;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	//cin >> T;
	
	for(int tc = 1; tc <= 10; tc++){
		// Input
		cin >> n;
		for(int i = 1; i <= n; i++){
			cin >> arr[i][0];
			L[i] = 0.0, R[i] = 0.0;
		}
		for(int i = 1; i <= n; i++){
			cin >> arr[i][1];
		}

		// Initial
		k = 0;
		
		// Solve Problem
		for(int i = 1; i <= n; i++){
			L[i] = calcLeft(i, i*1.0);
			R[i] = calcRight(i, i*1.0);
		}

		for(int i = 1; i <= n-1; i++){
			if(L[i] == R[i]){
				result[k++] = i*1.0;
				continue;
			}
			binarySearch(arr[i][0], arr[i+1][0], i);
		}
		
		
		// Output
		cout << "#" << tc << " ";
		cout.setf(ios::fixed);
		cout.setf(ios::showpoint);
		cout.precision(10);
		for(int i = 0; i < k; i++){
			cout << result[i] << " ";
		}
		cout << endl;
	}

	return 0;
 }