fork(3) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define pb push_back
  5. typedef long long LL;
  6.  
  7. int n;
  8. double x[11000], y[11000];
  9. double w[11000];
  10. double sx,sy;
  11. double tx,ty;
  12.  
  13. void solve(int test){
  14. 	cout << "Case #" << test + 1 << ": " ;
  15. 	cin >> n;
  16.  
  17. 	vector<pair<double, double> > vtx,vty;
  18. 	double S=0;
  19. 	for(int i=0; i<n; i++){
  20. 		cin >> tx >> ty >> w[i];
  21. 		//Transform
  22. 		x[i] = (tx+ty);
  23. 		y[i] = (ty-tx);		
  24. 		vtx.pb( {x[i] , w[i] } );
  25. 		vty.pb( {y[i], w[i] } );
  26. 		S += w[i];
  27. 	}
  28.  
  29. 	//Find median
  30. 	sort(vtx.begin(), vtx.end());
  31. 	sort(vty.begin(), vty.end());
  32.  
  33.   	int k = 0;
  34.   	double sum = S - vtx[0].second; 
  35.  
  36.   	while(sum > S/2){
  37.     	++k;
  38.     	sum -= vtx[k].second;;
  39.   	}	
  40.  
  41. 	double rx = vtx[k].first;
  42. 	if(sum == S/2){
  43. 		rx = (rx + vtx[k+1].first)/2;
  44. 	}
  45.  
  46. 	k = 0;
  47.   	sum = S - vty[0].second; 
  48.  
  49.   	while(sum > S/2){
  50.     	++k;
  51.     	sum -= vty[k].second;;
  52.   	}	
  53. 	double ry = vty[k].first;;
  54. 	if(sum == S/2){	
  55. 		ry = (ry + vty[k+1].first)/2;
  56. 	}
  57. 	double res = 0;
  58. 	for(int i=0; i<n; i++){
  59. 		res += (abs(rx-x[i]) + abs(ry-y[i]) )*w[i];
  60. 	}
  61.  
  62. 	cout << setprecision(7) << fixed << res/2 << endl;
  63. }
  64.  
  65. int ntest;
  66. int main(){
  67. 	cin >> ntest;
  68. 	for(int test=0; test<ntest; test++){
  69. 		solve(test);
  70. 	}
  71. 	return 0;
  72. }
Success #stdin #stdout 0s 16312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/IYRunA
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!