fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/MTRn2I
language:
C++ (gcc 8.3)
created:
8 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!