fork download
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <stdio.h>
  4. #include <set>
  5. #include <vector>
  6. #include <map>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <memory.h>
  10. #include <string>
  11. #include <sstream>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <cassert>
  15.  
  16. #include <math.h>
  17.  
  18. #define FF first
  19. #define SS second
  20. #define MP make_pair
  21. #define PB push_back
  22.  
  23. #define MOD 1000000007
  24. #define INF 2000000000
  25.  
  26. #define PI 3.141592653
  27.  
  28. using namespace std;
  29.  
  30. typedef long long LL;
  31. typedef pair<int,int> PII;
  32.  
  33. const int MAXN = 1010;
  34. double x[MAXN], y[MAXN]; int a[MAXN];
  35.  
  36. const int MAGIC = 20010;
  37.  
  38. int n; double m;
  39.  
  40. bool cmp(int i, int j) { return y[i] - m * x[i] < y[j] - m * x[j]; }
  41.  
  42. vector<int> indices;
  43.  
  44. int main() {
  45. cin >> n; int atot = 0;
  46.  
  47. for (int i = 0; i < n; i++) {
  48. cin >> x[i] >> y[i] >> a[i];
  49. atot += a[i];
  50. }
  51.  
  52. for (int i = 0; i < n; i++) indices.PB(i);
  53.  
  54. srand((unsigned) time(NULL));
  55.  
  56. int res = atot;
  57.  
  58. for (int i = 0; i < MAGIC; i++) {
  59. double A = ((double)rand()/(double)RAND_MAX);
  60. A = (A - 0.5) * PI;
  61. m = tan(A);
  62.  
  63. sort(indices.begin(), indices.end(), cmp);
  64.  
  65. int acurr = 0;
  66.  
  67. for (int i = 0; i < n; i++) {
  68. acurr += a[indices[i]];
  69. res = min(res, abs(atot - 2 * acurr));
  70. }
  71. }
  72.  
  73. printf("%d\n", res);
  74. return 0;
  75. }
Success #stdin #stdout 0s 3124KB
stdin
Standard input is empty
stdout
0