Little John has drawn $N$ stars on his paper where each star has a weight $v_i$. He draws a straight line that divides the paper into two parts such that each part has a subset of stars in them. Let the weight of each part be the summation of weights of the stars in the part. He wants to draw the line such that the difference in the sum of weights between the two parts is as small as possible while maximizing the smaller part's weight.  

Your task is to compute the weight of smaller part corresponding to this line where no stars are allowed to be on the line and line can be of any slope.  

Input Format 

The first line of the input contains an integer $N$. 

Each of next $N$ lines contains three integers $x_i$ and $y_i$ specifying the positions of $i^{\mbox{th}}$ star and $v_i$. 

No three points lie on a line.  

Constraints 

$1\leq N\leq100$ 

$-10^9\leq x_i,y_i\leq10^9$ 

$1\leq v_i\leq1000$  

Output Format 

Print an integer being the answer to the test.  

Sample Input 0  

4
1 1 2
-1 1 2
-1 -1 4
1 -1 5

Sample Output 0  

6

Explanation 

You can imagine a line along the $Y-axis$ and see that point $(-1,1)$ and $(-1,-1)$ lie on left side summing up to 6, while the other side has sum as $5+2=7$.  

Sample Input 1

10
748798831 -200797120 595
-774675771 179630170 159
-338760201 945958360 750
955629379 -312997434 516
755005057 -672683474 405
-743176829 190325067 86
-301478753 -718170081 923
-795908444 985440803 854
-102868895 671114060 246
-698209449 12550066 190

Sample Output 1

2358

Explanation  

$[595,159,405,86,923,190]$ and $[516,750,854,246]$ are two sets of weights.

Source: hackerrank | Difficulty: MEDIUM
Tags: Geometry


Solutions:
import random
n = int(input())
points = []
count = 0
for i in range(n):
	points.append([int(j) for j in input().split()])
	count += points[i][2]
half = count / 2
pos = 0
maxMin = 0
while pos < 1000:
	x1 = random.randrange(1, 10 ** 9)
	x2 = random.randrange(1, 10 ** 9)
	y1 = random.randrange(1, 10 ** 9)
	y2 = random.randrange(1, 10 ** 9)
	if x1 == x2:
		continue
	x = x2 - x1
	y = y2 - y1
	s = x * x + y * y
	ps = {}
	good = True
	for i in range(n):
		xs = x * (points[i][0] * x + points[i][1] * y) / s
		if xs in ps:
			good = False
			break
		ps[xs] = points[i][2]
	if not good:
		continue
	sps = sorted(ps.items(), key=lambda x: x[0])
	curr = 0
	foll = 0
	for i in sps:
		curr = foll
		foll += i[1]
		if foll > half:
			val = max(curr, count - foll)
			if val > maxMin:
				maxMin = val
			break
	pos += 1
print(maxMin)


def crossProd(A, B):
	return A[0] * B[1] - A[1] * B[0]
N = int(input())
(stars, s) = ([], 0)
for n in range(N):
	(x, y, v) = [int(x) for x in input().split(' ')]
	stars.append(((x, y), v))
	s += v
dmin = s
for i in range(N):
	for j in range(i):
		A = (stars[j][0][0] - stars[i][0][0], stars[j][0][1] - stars[i][0][1])
		d = 0
		for k in range(N):
			if k != i and k != j:
				B = (stars[k][0][0] - stars[i][0][0], stars[k][0][1] - stars[i][0][1])
				if crossProd(A, B) > 0:
					d += stars[k][1]
				else:
					d -= stars[k][1]
		if d < 0:
			d = -d
		(Vi, Vj) = (stars[i][1], stars[j][1])
		if Vi > Vj:
			(Vi, Vj) = (Vj, Vi)
		if d > Vj - Vi:
			d -= Vj - Vi
		else:
			d = Vj - Vi - d
		if d < dmin:
			dmin = d
print((s - dmin) // 2)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


import itertools
import math

def calculateside(a, b, c):
	(x1, y1) = (a[0], a[1])
	(x2, y2) = (b[0], b[1])
	(x3, y3) = (c[0], c[1])
	z = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
	if z > 0:
		return 'UP'
	if z < 0:
		return 'DOWN'
	if z == 0:
		return 'ON'
numstars = int(input())
stars = []
for i in range(numstars):
	stars.append(input().split())
z = list(itertools.combinations(stars, 2))
diff = None
for el in z:
	a = (int(el[0][0]), int(el[0][1]))
	b = (int(el[1][0]), int(el[1][1]))
	up = 0
	down = 0
	for star in stars:
		c = (int(star[0]), int(star[1]))
		value = calculateside(a, b, c)
		if value == 'ON':
			pass
		elif value == 'UP':
			up += int(star[2])
		elif value == 'DOWN':
			down += int(star[2])
		else:
			print('Strange')
			pass
	w1 = int(el[0][2])
	w2 = int(el[1][2])
	if up > down:
		if w1 > w2:
			down = down + w1
			up = up + w2
		else:
			down = down + w2
			up = up + w1
	elif up < down:
		if w1 > w2:
			up = up + w1
			down = down + w2
		else:
			up = up + w2
			down = down + w1
	else:
		down = down + w1
		up = up + w2
	if diff == None:
		diff = math.fabs(up - down)
		if up > down:
			answer = down
		else:
			answer = up
	elif diff > math.fabs(up - down):
		diff = math.fabs(up - down)
		if up > down:
			answer = down
		else:
			answer = up
	else:
		pass
print(answer)


import sys
n = int(input())
stars = []
for i in range(n):
	(x, y, v) = map(int, input().split(' '))
	stars.append((x, y, v))
mindiff_groupvalue = 0
mindiff = sys.maxsize
for a in stars:
	for b in stars:
		leftgroup = 0
		rightgroup = 0
		for c in stars:
			if a == b or b == c or a == c:
				continue
			cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
			if cross < 0:
				leftgroup += c[2]
			else:
				rightgroup += c[2]
		diffAB = abs(leftgroup + a[2] - rightgroup - b[2])
		diffBA = abs(leftgroup + b[2] - rightgroup - a[2])
		if diffAB < diffBA and diffAB < mindiff:
			mindiff = diffAB
			mindiff_groupvalue = min(leftgroup + a[2], rightgroup + b[2])
		elif diffBA < diffAB and diffBA < mindiff:
			mindiff = diffBA
			mindiff_groupvalue = min(leftgroup + b[2], rightgroup + a[2])
print(mindiff_groupvalue)


class star:

	def __init__(self, x, y, v):
		self.x = x
		self.y = y
		self.v = v
n = int(input())
stars = []
for i in range(n):
	(x, y, v) = (int(d) for d in input().split())
	stars += [star(x, y, v)]
bestDiv = 0
for i in range(n):
	for j in range(i + 1, n):
		totalL = 0
		totalR = 0
		mx = stars[j].y - stars[i].y
		my = stars[i].x - stars[j].x
		b = stars[i].y * stars[j].x - stars[j].y * stars[i].x
		for k in range(n):
			if k != i and k != j:
				if mx * stars[k].x + my * stars[k].y + b > 0:
					totalL += stars[k].v
				else:
					totalR += stars[k].v
		possibleTotals = [(totalL + stars[i].v + stars[j].v, totalR), (totalL + stars[i].v, totalR + stars[j].v), (totalL + stars[j].v, totalR + stars[i].v), (totalL, totalR + stars[i].v + stars[j].v)]
		for total in possibleTotals:
			bestDiv = max(bestDiv, min(total[0], total[1]))
print(bestDiv)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


pts = [[int(i) for i in input().split()] for _ in range(int(input()))]
N = len(pts)
res = 0
s = 0
for p in pts:
	s += p[2]
for pi in range(N):
	for pj in range(N):
		t = 0
		for pk in range(N):
			if (pts[pi][1] - pts[pk][1]) * (pts[pj][0] - pts[pk][0]) <= (pts[pj][1] - pts[pk][1]) * (pts[pi][0] - pts[pk][0]):
				t += pts[pk][2]
		if t <= s - t and t > res:
			res = t
		elif t >= s - t and s - t > res:
			res = s - t
print(res)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


def main():
	npts = int(input())
	pt = [tuple((int(fld) for fld in input().split())) for _ in range(npts)]
	assert all((len(p) == 3 for p in pt))
	print(solve(pt))

def solve(pt):
	best = (sum((p[2] for p in pt)), 0)
	for (i, p0) in enumerate(pt):
		for (j, p1) in zip(range(i), pt):
			v0 = v1 = 0
			(dx, dy) = [p0[k] - p1[k] for k in (0, 1)]
			for p in pt:
				discr = dy * (p[0] - p0[0]) - dx * (p[1] - p0[1])
				if discr < 0:
					v0 += p[2]
				elif discr > 0:
					v1 += p[2]
			candidate = bestforline(v0, v1, p0[2], p1[2])
			best = min(candidate, best)
	return -best[1]

def bestforline(v0, v1, p0v, p1v):
	addlist = [(p0v + p1v, 0), (p0v, p1v)]
	addlist += [(y, x) for (x, y) in addlist]
	cand = []
	for (a0, a1) in addlist:
		(w0, w1) = (v0 + a0, v1 + a1)
		cand.append((abs(w0 - w1), -min(w0, w1)))
	return min(cand)
main()


from math import pi, atan2
N = int(input())
pts = []
offset_pts = []
for i in range(N):
	(x, y, v) = [int(i) for i in input().split()]
	pts.append((x, y, v))
	offset_pts.append((x + 100000.0, y + 100000.0))
	offset_pts.append((x + 100000.0, y - 100000.0))
	offset_pts.append((x - 100000.0, y - 100000.0))
	offset_pts.append((x - 100000.0, y + 100000.0))
result = 0
for i in range(len(offset_pts)):
	for j in range(i + 1, len(offset_pts)):
		c1 = c2 = 0
		(p0, p1) = (offset_pts[i], offset_pts[j])
		n = (p0[1] - p1[1], p1[0] - p0[0])
		for p in range(N):
			p2 = pts[p]
			u = (p2[0] - p0[0], p2[1] - p0[1])
			un = u[0] * n[0] + u[1] * n[1]
			if un >= 0:
				c1 += p2[2]
			else:
				c2 += p2[2]
		result = max(result, min(c1, c2))
print(result)


N = int(input())
pts = []
weights = []
s = 0
for i in range(N):
	tmp = input().split()
	pts.append((int(tmp[0]), int(tmp[1]), int(tmp[2])))
	s += int(tmp[2])
min_d = s
max_w = 0
for i in pts:
	for j in pts:
		if i != j:
			c = i[2] + j[2]
			u = i[0] - j[0]
			v = i[1] - j[1]
			w = i[0] * v - i[1] * u
			for k in pts:
				if k != i and k != j:
					if -u * k[1] + v * k[0] > w:
						c += k[2]
			if abs(2 * c - s) < min_d:
				min_d = abs(2 * c - s)
				max_w = min(s - c, c)
print(max_w)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


import math
EPSI = 1e-08

def calcAB(p0, p1):
	if p0[1] == p1[1]:
		return (0, p0[1])
	a = (p0[1] - p1[1]) / (p0[0] - p1[0])
	b = p0[1] - a * p0[0]
	return (a, b)

def splitPV(coords, ws, xs, wpp, ni, nj):
	left = right = 0
	for i in range(len(ws)):
		if i == ni or i == nj:
			continue
		p = coords[i]
		w = ws[i]
		if p[0] < xs:
			left += w
		elif p[0] > xs:
			right += w
	if left < right:
		left += wpp
	else:
		right += wpp
	return (abs(left - right), min(left, right))

def splitP(coords, vs, ca, cb, wpp, ni, nj):
	left = right = 0
	for i in range(len(ws)):
		if i == ni or i == nj:
			continue
		p = coords[i]
		w = ws[i]
		func_v = p[0] * ca + cb
		if func_v < p[1]:
			left += w
		elif func_v > p[1]:
			right += w
	if left < right:
		left += wpp
	else:
		right += wpp
	return (abs(left - right), min(left, right))
coords = []
ws = []
n = int(input())
for _ in range(n):
	(x, y, w) = map(int, input().split())
	coords.append([x, y])
	ws.append(w)
diff = 99999999999999
minw = 0
plen = len(ws)
for i in range(plen):
	for j in range(i + 1, plen):
		p0 = coords[i]
		p1 = coords[j]
		wpp = ws[i] + ws[j]
		min_diff = minw = 0
		if abs(p0[0] - p1[0]) <= EPSI:
			xs = p0[0]
			(min_diff, minw) = splitPV(coords, ws, xs, wpp, i, j)
		else:
			(a, b) = calcAB(p0, p1)
			(min_diff, minw) = splitP(coords, ws, a, b, wpp, i, j)
		if min_diff < diff:
			diff = min_diff
			grp = minw
print(grp)


def turnRight(p1, p2, p3):
	d = p1[0] * p2[1] + p1[1] * p3[0] + p2[0] * p3[1] - p1[0] * p3[1] - p2[0] * p1[1] - p3[0] * p2[1]
	return d < 0

def countHalf(a, b, lis):
	res = 0
	for x in lis:
		if turnRight(a, b, x):
			res += x[2]
	return res

def diff(a, b):
	return abs(a - b)
n = int(input())
lis = []
vsum = 0
for _ in range(n):
	(x, y, v) = list(map(int, input().split()))
	lis.append((x, y, v))
	vsum += v
mindiff = vsum
for i in range(n):
	for j in range(i + 1, n):
		h1 = countHalf(lis[i], lis[j], lis)
		h2 = vsum - h1
		v1 = lis[i][2]
		v2 = lis[j][2]
		mindiff = min(mindiff, diff(h1, h2))
		mindiff = min(mindiff, diff(h1 + v1, h2 - v1))
		mindiff = min(mindiff, diff(h1 + v2, h2 - v2))
		mindiff = min(mindiff, diff(h1 + v1 + v2, h2 - v1 - v2))
print((vsum - mindiff) // 2)


def above(m, x0, y0, point):
	if m == 'inf':
		return point[0] > x0
	return point[1] > m * (point[0] - x0) + y0
n = int(input())
best = 0
points = [[]] * n
for i in range(n):
	points[i] = list(map(int, input().split()))
total = sum((point[2] for point in points))
for i in range(n):
	x0 = points[i][0]
	y0 = points[i][1]
	v = points[i][2]
	for j in range(i):
		x1 = points[j][0]
		y1 = points[j][1]
		w = points[j][2]
		m = 'inf' if x1 == x0 else (y1 - y0) / (x1 - x0)
		a = sum((point[2] for (index, point) in enumerate(points) if above(m, x0, y0, point) and i != index != j))
		b = total - a - v - w
		max_min = max(min(a + v + w, b), min(a + v, b + w), min(a + w, b + v), min(a, b + v + w))
		if max_min > best:
			best = max_min
print(best)


from sys import stdin
n = int(stdin.readline())
points = []
w = 0
for ni in range(n):
	points.append(tuple([int(z) for z in stdin.readline().split()]))
for p1 in points:
	for p2 in points:
		if p1 == p2:
			continue
		w1 = 0
		w2 = 0
		for p in points:
			if (p2[0] - p1[0]) * (p[1] - p1[1]) - (p2[1] - p1[1]) * (p[0] - p1[0]) >= 0:
				w1 += p[2]
			else:
				w2 += p[2]
		w = max(w, min(w1, w2))
print(w)


nn = int(input())
stars = []
for i1 in range(nn):
	inp = list(map(int, input().split()))
	stars.append(inp)
diff = 10000000000
for i1 in range(nn):
	for i2 in range(i1 + 1, nn):
		bb = stars[i1][1]
		x1 = stars[i1][0]
		v1 = stars[i1][2]
		v2 = stars[i2][2]
		s_up = 0
		s_lo = 0
		if stars[i2][0] == stars[i1][0]:
			for j1 in range(nn):
				if j1 != i1 and j1 != i2:
					if stars[j1][0] < x1:
						s_up = s_up + stars[j1][2]
					elif stars[j1][0] > x1:
						s_lo = s_lo + stars[j1][2]
		else:
			aa = (stars[i2][1] - stars[i1][1]) / (stars[i2][0] - stars[i1][0])
			for j1 in range(nn):
				if j1 != i1 and j1 != i2:
					dy = stars[j1][1] - aa * (stars[j1][0] - x1) - bb
					if dy >= 0:
						s_up = s_up + stars[j1][2]
					elif dy < 0:
						s_lo = s_lo + stars[j1][2]
		ds = s_up - s_lo
		diff1 = abs(ds + v1 + v2)
		if diff1 < diff:
			diff = diff1
			small = min(s_up + v1 + v2, s_lo)
			conf = [i1, i2, 0]
		diff1 = abs(ds + v1 - v2)
		if diff1 < diff:
			diff = diff1
			small = min(s_up + v1, s_lo + v2)
			conf = [i1, i2, 1]
		diff1 = abs(ds - v1 + v2)
		if diff1 < diff:
			diff = diff1
			small = min(s_up + v2, s_lo + v1)
			conf = [i1, i2, 2]
		diff1 = abs(ds - v1 - v2)
		if diff1 < diff:
			diff = diff1
			small = min(s_up, s_lo + v1 + v2)
			conf = [i1, i2, 3]
print(small)


n = int(input())
stars = []
max_min_half = 0
for _ in range(n):
	stars += [list(map(int, input().split()))]
all_stars_sum = sum([z for (x, y, z) in stars])
stars.sort()
for i in range(n):
	for j in range(i):
		sum_of_half = 0
		dx = stars[i][0] - stars[j][0]
		dy = stars[i][1] - stars[j][1]
		if stars[i][0] == stars[j][0]:
			for star in stars:
				sum_of_half += star[2] if star[0] <= stars[i][0] else 0
		else:
			for star in stars:
				if star[1] * dx >= stars[j][1] * dx + (star[0] - stars[j][0]) * dy:
					sum_of_half += star[2]
		max_min_half = max([max_min_half, min([all_stars_sum - sum_of_half, sum_of_half])])
		max_min_half = max([max_min_half, min([all_stars_sum - sum_of_half + stars[i][2], sum_of_half - stars[i][2]])])
		max_min_half = max([max_min_half, min([all_stars_sum - sum_of_half + stars[j][2], sum_of_half - stars[j][2]])])
		max_min_half = max([max_min_half, min([all_stars_sum - sum_of_half + stars[i][2] + stars[j][2], sum_of_half - stars[i][2] - stars[j][2]])])
print(max_min_half)


import sys
n = int(sys.stdin.readline())
stars = []
for i in range(n):
	star = tuple((int(x) for x in sys.stdin.readline().split()))
	stars.append(star)
delta_min = int(1e+50)
small_max = 0
for i in range(n):
	for j in range(i + 1, n):
		ux = stars[i][0] - stars[j][0]
		uy = stars[i][1] - stars[j][1]
		count1 = 0
		count2 = 0
		for k in range(n):
			if k == i or k == j:
				continue
			vx = stars[i][0] - stars[k][0]
			vy = stars[i][1] - stars[k][1]
			kw = stars[k][2]
			det = ux * vy - uy * vx
			if det > 0:
				count1 += kw
			else:
				count2 += kw
		for w in (stars[i][2], stars[j][2]):
			if count1 < count2:
				count1 += w
			else:
				count2 += w
		if count1 < count2:
			delta = count2 - count1
			small = count1
		else:
			delta = count1 - count2
			small = count2
		if delta < delta_min:
			delta_min = delta
			small_max = small
print(small_max)


from itertools import combinations
V = []
S = 0
D = set()
N = int(input())
for n in range(N):
	(x, y, v) = [int(m) for m in input().split()]
	S += v
	V.append((x, y, v))
for i in range(len(V)):
	for j in range(i + 1, len(V)):
		(a, b) = (V[i], V[j])
		if a[0] != b[0]:
			S1 = sum((v[2] for v in V if v != a and v != b and (v[1] < (a[1] - b[1]) / (a[0] - b[0]) * (v[0] - b[0]) + b[1])))
		else:
			S1 = sum((v[2] for v in V if v != a and v != b and (v[0] < a[0])))
		D.add(min(S1, S - S1))
		D.add(min(S1 + a[2], S - (S1 + a[2])))
		D.add(min(S1 + b[2], S - (S1 + b[2])))
		D.add(min(S1 + a[2] + b[2], S - (S1 + a[2] + b[2])))
print(max(D))


from itertools import combinations

class Point:

	def __init__(self, x, y, v):
		self.x = x
		self.y = y
		self.v = v
pts = []
n = int(input())
for i in range(n):
	p = Point(*(int(a) for a in input().split()))
	pts.append(p)
w = 0
for (i, j) in combinations(range(n), 2):
	(a, b) = (pts[i], pts[j])
	(w1, w2) = (0, 0)
	for p in pts:
		t = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)
		if t > 0:
			w1 += p.v
		elif t < 0:
			w2 += p.v
	w = max(w, min(w1 + a.v, w2 + b.v), min(w1 + b.v, w2 + a.v), min(w1 + a.v + b.v, w2), min(w1, w2 + a.v + b.v))
print(w)


import sys
L = []

def getSide(p1, p2, px):
	return (p2[0] - p1[0]) * (px[1] - p1[1]) - (p2[1] - p1[1]) * (px[0] - p1[0])

def getWeights(i, j):
	w1 = 0
	w2 = 0
	for k in range(len(L)):
		if k != i and k != j:
			side = getSide(L[i], L[j], L[k])
			if side > 0:
				w1 += L[k][2]
			elif side < 0:
				w2 += L[k][2]
			else:
				print('onaline')
				continue
	wl1 = w1 + L[i][2]
	wl2 = w2 + L[j][2]
	wr1 = w1 + L[j][2]
	wr2 = w2 + L[i][2]
	dl = abs(wl1 - wl2)
	dr = abs(wr1 - wr2)
	if dl < dr:
		return (wl1, wl2, dl)
	else:
		return (wr1, wr2, dr)
N = int(input())
for i in range(N):
	[x, y, v] = [int(x) for x in input().split(' ')]
	L.append((x, y, v))
mind = sys.maxsize
for i in range(len(L)):
	for j in range(i + 1, len(L)):
		w = getWeights(i, j)
		if w[2] < mind:
			mind = w[2]
			res = w
print(min(res[0], res[1]))


class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __sub__(self, other):
		return Point(self.x - other.x, self.y - other.y)

def det(p, q):
	return p.x * q.y - p.y * q.x
N = int(input())
P = [None] * N
v = [None] * N
for i in range(N):
	(x, y, v[i]) = map(int, input().split())
	P[i] = Point(x, y)
best_diff = float('inf')
for i in range(N):
	for j in range(N):
		q = P[i] - P[j]
		part1 = sum((v[k] for k in range(N) if det(q, P[k] - P[j]) >= 0))
		part2 = sum(v) - part1
		if abs(part1 - part2) < best_diff:
			best_diff = abs(part1 - part2)
			small = min(part1, part2)
print(small)


from math import inf

def f(x, k, c):
	return k * x + c

def div(i, j, S):
	x0 = S[i][0]
	y0 = S[i][1]
	x1 = S[j][0]
	y1 = S[j][1]
	if x0 != x1:
		k = (y1 - y0) / (x1 - x0)
		c = y0 - x0 * k
		D0 = []
		D1 = []
		D2 = []
		D3 = []
		U0 = []
		U1 = []
		U2 = []
		U3 = []
		for n in range(len(S)):
			xn = S[n][0]
			yn = S[n][1]
			wn = S[n][2]
			yf = f(xn, k, c)
			if yn < yf:
				D0.append(wn)
				D1.append(wn)
				D2.append(wn)
				D3.append(wn)
			elif yn > yf:
				U0.append(wn)
				U1.append(wn)
				U2.append(wn)
				U3.append(wn)
			else:
				if xn <= x0:
					U0.append(wn)
					D1.append(wn)
				else:
					D0.append(wn)
					U1.append(wn)
				if xn <= x1:
					U2.append(wn)
					D3.append(wn)
				else:
					D2.append(wn)
					U3.append(wn)
	else:
		U0 = []
		U1 = []
		U2 = []
		U3 = []
		D0 = []
		D1 = []
		D2 = []
		D3 = []
		for n in range(len(S)):
			yn = S[n][1]
			xn = S[n][0]
			wn = S[n][2]
			if xn < x0:
				U0.append(wn)
				U1.append(wn)
				U2.append(wn)
				U3.append(wn)
			elif xn > x0:
				D0.append(wn)
				D1.append(wn)
				D2.append(wn)
				D3.append(wn)
			else:
				if yn <= y1:
					U0.append(wn)
					D1.append(wn)
				else:
					D0.append(wn)
					U1.append(wn)
				if yn <= y0:
					U2.append(wn)
					D3.append(wn)
				else:
					D2.append(wn)
					U3.append(wn)
	m = inf
	mi = -1
	su0 = sum(U0)
	su1 = sum(U1)
	su2 = sum(U2)
	su3 = sum(U3)
	sd0 = sum(D0)
	sd1 = sum(D1)
	sd2 = sum(D2)
	sd3 = sum(D3)
	if abs(su0 - sd0) < m:
		m = abs(su0 - sd0)
		mi = 0
	if abs(su1 - sd1) < m:
		m = abs(su1 - sd1)
		mi = 1
	if abs(su2 - sd2) < m:
		m = abs(su2 - sd2)
		mi = 2
	if abs(su3 - sd3) < m:
		m = abs(su3 - sd3)
		mi = 3
	if mi == 0:
		return (m, min(su0, sd0))
	if mi == 1:
		return (m, min(su1, sd1))
	if mi == 2:
		return (m, min(su2, sd2))
	if mi == 3:
		return (m, min(su3, sd3))

def solve(S, N):
	(M, MS) = (inf, 0)
	for i in range(N):
		for j in range(i + 1, N):
			(m, ms) = div(i, j, S)
			if m < M:
				M = m
				MS = ms
	print(MS)
N = int(input())
S = []
for n0 in range(N):
	(x, y, w) = (int(a) for a in input().split())
	S.append((x, y, w))
solve(S, N)


import sys

def tuple_gen(aa, l):
	if l > len(aa):
		return
	stack = [(0, tuple())]
	while stack:
		(i, t) = stack.pop()
		if len(t) == l:
			yield tuple((aa[j] for j in t))
		else:
			for j in range(i, len(aa)):
				stack.append((j + 1, t + (j,)))

def get_z(p1, p2, p3):
	v1 = (p3[0] - p1[0], p3[1] - p1[1])
	v2 = (p3[0] - p2[0], p3[1] - p2[1])
	return v1[0] * v2[1] - v1[1] * v2[0]

def solve(aa):
	(u, v) = (None, None)
	for (p1, p2) in tuple_gen(aa, 2):
		(a, b) = (0, 0)
		for p in aa:
			z = get_z(p1, p2, p)
			if z < 0:
				b += p[-1]
			elif z > 0:
				a += p[-1]
		for (sm1, sm2) in ((a + p1[-1] + p2[-1], b), (a + p1[-1], b + p2[-1]), (a + p2[-1], b + p1[-1]), (a, b + p1[-1] + p2[-1])):
			if sm1 < sm2:
				(sm1, sm2) = (sm2, sm1)
			if u is None:
				(u, v) = (sm1, sm2)
			elif u - v > sm1 - sm2:
				(u, v) = (sm1, sm2)
			elif u - v == sm1 - sm2 and sm2 < v:
				(u, v) = (sm1, sm2)
	return v
n = int(input())
aa = list()
for _ in range(n):
	(x, y, w) = map(int, input().split())
	aa.append((x, y, w))
print(solve(aa))


import math
n = int(input())
arr = []
M = 0
for _ in range(n):
	(x, y, m) = [int(val) for val in input().split()]
	arr.append((x, y, m))
	M += m
delta = M
for i in range(n):
	for j in range(i + 1, n):
		dx = arr[j][0] - arr[i][0]
		dy = arr[j][1] - arr[i][1]
		(lm, rm) = (0, 0)
		if abs(dx) > abs(dy):
			k = dy / dx
			b = arr[j][1] - k * arr[j][0]
			for m in range(n):
				if m != i and m != j:
					if arr[m][1] > k * arr[m][0] + b:
						lm += arr[m][2]
					else:
						rm += arr[m][2]
		else:
			k = dx / dy
			b = arr[j][0] - k * arr[j][1]
			for m in range(n):
				if m != i and m != j:
					if arr[m][0] > k * arr[m][1] + b:
						lm += arr[m][2]
					else:
						rm += arr[m][2]
		delta = min(abs(lm + arr[j][2] - rm - arr[i][2]), abs(lm - arr[j][2] - rm + arr[i][2]), abs(lm + arr[j][2] - rm + arr[i][2]), abs(lm - arr[j][2] - rm - arr[i][2]), delta)
print((M - delta) // 2)


from fractions import Fraction
N = int(input())
pts = []
for i in range(N):
	pts.append([int(s) for s in input().split()])
if N < 1:
	print(0)
	exit()
slopes = set()
for i in range(N):
	for j in range(i):
		dx = pts[i][0] - pts[j][0]
		if dx:
			dy = pts[i][1] - pts[j][1]
			slopes.add(Fraction(dy, dx))
slopes.add(Fraction(0))
slopes.add(2 * max(slopes))
slopes.add(2 * min(slopes))
mid = []
t = None
for s in sorted(slopes):
	if t != None:
		mid.append((s + t) / 2)
	t = s
total = 0
for p in pts:
	total += p[2]
best = 0
for s in mid:
	s1 = s.denominator
	s0 = s.numerator
	pts.sort(key=lambda p: p[0] * s0 + p[1] * s1)
	t = 0
	for p in pts:
		t += p[2]
		if 2 * t >= total:
			if total - t > best:
				best = total - t
			t -= p[2]
			if t > best:
				best = t
			break
print(best)


import math
import os
import random
import re
import sys
import itertools, sys

class Point:

	def __init__(self, x, y, v):
		(self.x, self.y, self.v) = (x, y, v)

	def __eq__(self, other):
		return isinstance(other, self.__class__) and self.__dict__ == other.__dict__

	def __ne__(self, other):
		return not self.__eq__(other)
N = int(sys.stdin.readline())
points = [Point(*list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
max_weight = 0
best_weight = lambda a, b: max(max_weight, min(a, b))
det = lambda a, b, c: (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
for (a, b) in itertools.combinations(points, 2):
	(above, below) = (0, 0)
	for c in (p for p in points if p != a and p != b):
		if det(a, b, c) > 0:
			above += c.v
		else:
			below += c.v
	max_weight = best_weight(above + a.v + b.v, below)
	max_weight = best_weight(above + a.v, below + b.v)
	max_weight = best_weight(above + b.v, below + a.v)
	max_weight = best_weight(above, below + a.v + b.v)
print(max_weight)


import random
n = int(input())
points = []
count = 0
for i in range(n):
	points.append([int(j) for j in input().split()])
	count += points[i][2]
half = count / 2
pos = 0
maxMin = 0
while pos < 1000:
	x1 = random.randrange(1, 10 ** 9)
	x2 = random.randrange(1, 10 ** 9)
	y1 = random.randrange(1, 10 ** 9)
	y2 = random.randrange(1, 10 ** 9)
	if x1 == x2:
		continue
	x = x2 - x1
	y = y2 - y1
	s = x * x + y * y
	ps = {}
	good = True
	for i in range(n):
		xs = x * (points[i][0] * x + points[i][1] * y) / s
		if xs in ps:
			good = False
			break
		ps[xs] = points[i][2]
	if not good:
		continue
	sps = sorted(ps.items(), key=lambda x: x[0])
	curr = 0
	foll = 0
	for i in sps:
		curr = foll
		foll += i[1]
		if foll > half:
			val = max(curr, count - foll)
			if val > maxMin:
				maxMin = val
			break
	pos += 1
print(maxMin)


import random
n = int(input())
points = []
count = 0
for i in range(n):
	points.append([int(j) for j in input().split()])
	count += points[i][2]
half = count / 2
pos = 0
maxMin = 0
while pos < 1000:
	x1 = random.randrange(1, 10 ** 9)
	x2 = random.randrange(1, 10 ** 9)
	y1 = random.randrange(1, 10 ** 9)
	y2 = random.randrange(1, 10 ** 9)
	if x1 == x2:
		continue
	x = x2 - x1
	y = y2 - y1
	s = x * x + y * y
	ps = {}
	good = True
	for i in range(n):
		xs = x * (points[i][0] * x + points[i][1] * y) / s
		if xs in ps:
			good = False
			break
		ps[xs] = points[i][2]
	if not good:
		continue
	sps = sorted(ps.items(), key=lambda x: x[0])
	curr = 0
	foll = 0
	for i in sps:
		curr = foll
		foll += i[1]
		if foll > half:
			val = max(curr, count - foll)
			if val > maxMin:
				maxMin = val
			break
	pos += 1
print(maxMin)


import random
n = int(input())
points = []
count = 0
for i in range(n):
	points.append([int(j) for j in input().split()])
	count += points[i][2]
half = count / 2
pos = 0
maxMin = 0
while pos < 1000:
	x1 = random.randrange(1, 10 ** 9)
	x2 = random.randrange(1, 10 ** 9)
	y1 = random.randrange(1, 10 ** 9)
	y2 = random.randrange(1, 10 ** 9)
	if x1 == x2:
		continue
	x = x2 - x1
	y = y2 - y1
	s = x * x + y * y
	ps = {}
	good = True
	for i in range(n):
		xs = x * (points[i][0] * x + points[i][1] * y) / s
		if xs in ps:
			good = False
			break
		ps[xs] = points[i][2]
	if not good:
		continue
	sps = sorted(ps.items(), key=lambda x: x[0])
	curr = 0
	foll = 0
	for i in sps:
		curr = foll
		foll += i[1]
		if foll > half:
			val = max(curr, count - foll)
			if val > maxMin:
				maxMin = val
			break
	pos += 1
print(maxMin)


import random
n = int(input())
points = []
count = 0
for i in range(n):
	points.append([int(j) for j in input().split()])
	count += points[i][2]
half = count / 2
pos = 0
maxMin = 0
while pos < 1000:
	x1 = random.randrange(1, 10 ** 9)
	x2 = random.randrange(1, 10 ** 9)
	y1 = random.randrange(1, 10 ** 9)
	y2 = random.randrange(1, 10 ** 9)
	if x1 == x2:
		continue
	x = x2 - x1
	y = y2 - y1
	s = x * x + y * y
	ps = {}
	good = True
	for i in range(n):
		xs = x * (points[i][0] * x + points[i][1] * y) / s
		if xs in ps:
			good = False
			break
		ps[xs] = points[i][2]
	if not good:
		continue
	sps = sorted(ps.items(), key=lambda x: x[0])
	curr = 0
	foll = 0
	for i in sps:
		curr = foll
		foll += i[1]
		if foll > half:
			val = max(curr, count - foll)
			if val > maxMin:
				maxMin = val
			break
	pos += 1
print(maxMin)


import random
n = int(input())
points = []
count = 0
for i in range(n):
	points.append([int(j) for j in input().split()])
	count += points[i][2]
half = count / 2
pos = 0
maxMin = 0
while pos < 1000:
	x1 = random.randrange(1, 10 ** 9)
	x2 = random.randrange(1, 10 ** 9)
	y1 = random.randrange(1, 10 ** 9)
	y2 = random.randrange(1, 10 ** 9)
	if x1 == x2:
		continue
	x = x2 - x1
	y = y2 - y1
	s = x * x + y * y
	ps = {}
	good = True
	for i in range(n):
		xs = x * (points[i][0] * x + points[i][1] * y) / s
		if xs in ps:
			good = False
			break
		ps[xs] = points[i][2]
	if not good:
		continue
	sps = sorted(ps.items(), key=lambda x: x[0])
	curr = 0
	foll = 0
	for i in sps:
		curr = foll
		foll += i[1]
		if foll > half:
			val = max(curr, count - foll)
			if val > maxMin:
				maxMin = val
			break
	pos += 1
print(maxMin)