Yandex.Contest.2015-r1.B.AC

// Author: Georgy Chebanov
// AC -> {GNU c++ 11 4.9, 0.794s, 380.00Kb}

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < (int)(n); ++i)

using namespace std;

const int N = 1000;

struct pt { int x, y; };

pt p[N];
int w[N];

int main() {
  int n;
  int a, b, c, s_up, s_down, cc;
  int ans, s_all;

  s_all = 0;
  cin >> n;
  forn(i, n) cin >> p[i].x >> p[i].y >> w[i];
  forn(i, n) s_all += w[i];

  ans = (n == 1 ? w[0] : 1e9);

  forn(i, n) forn(j, i) {
    a = p[i].y - p[j].y;
    b = p[j].x - p[i].x;
    c = a * p[i].x + b * p[i].y;

    s_up = 0;

    swap(p[i], p[n-1]);
    swap(w[i], w[n-1]);

    swap(p[j], p[n-2]);
    swap(w[j], w[n-2]);

    forn(k, n - 2) {
      cc = (a * 1ll * p[k].x + b * 1ll * p[k].y - c) >> 31;
      s_up += w[k] & cc;
    }

    swap(p[j], p[n-2]);
    swap(w[j], w[n-2]);

    swap(p[i], p[n-1]);
    swap(w[i], w[n-1]);

    s_down = s_all - w[i] - w[j] - s_up;

    ans = min(ans, abs( (s_up + w[i] + w[j]) - (s_down) ));
    ans = min(ans, abs( (s_down + w[i] + w[j]) - (s_up) ));

    ans = min(ans, abs( (s_up + w[i]) - (s_down + w[j]) ));
    ans = min(ans, abs( (s_down + w[i]) - (s_up + w[j]) ));
  }
  cout << ans << '\n';
  return 0;
}