Yandex.Contest.2015-r1.B.AC.cpp.2

// Author: Georgy Chebanov
// AC -> {GNU c++ 4.9.2, 220ms, 380.00Kb}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 2000;

int w[N];
int px[N];
int py[N];

__attribute__((target("sse4.1")))
__attribute__((optimize("O3")))
void solve() {
  int n, a, b, c, s_up, s_down, cc, ans, wn1, wn2, s_all = 0;
  cin >> n;
  forn(i, n) {
    cin >> px[i] >> py[i] >> w[i];
    s_all += w[i];
  }
  ans = (n == 1 ? w[0] : 1e9);
  forn(i, n) forn(j, i) {
    a = py[i] - py[j];
    b = px[j] - px[i];
    c = a * px[i] + b * py[i];
    wn1 = wn2 = s_up = 0;

    swap(w[i], wn1);
    swap(w[j], wn2);

    forn(k, n) {
      cc = (px[k] * a + py[k] * b - c) >> 31;
      s_up += w[k] & cc;
    }

    swap(w[j], wn2);
    swap(w[i], wn1);

    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';
}

int main() {
  solve();
  return 0;
}