Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

[Flappy Bird] is on a screen with height $H$ pixels (a 2D plane where the $y$-axis corresponds to the vertical direction). There are $N$ vertical obstacles in the room (numbered $1$ through $N$); for each valid $i$, the coordinates of the *endpoint* of the $i$-th obstacle are $(x_{i}, a_{i})$. There are two types of obstacles: 
Type 0: A line segment between the points $(x_{i}, 0)$ and $(x_{i}, a_{i})$, i.e. upwards from the floor.
Type 1: A line segment between the points $(x_{i}, H)$ and $(x_{i}, a_{i})$, i.e. downwards from the ceiling.

For each obstacle, you need to find the number of endpoints of other obstacles (not including itself) that are visible from its endpoint. Two endpoints are visible from each other if the line segment joining them does not intersect or touch any other obstacle. Note that each obstacle has exactly one endpoint.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $H$ and $N$.
The following $N$ lines describe the obstacles. For each valid $i$, the $i$-th of these lines contains three space-separated integers $t_{i}$, $x_{i}$ and $a_{i}$, where $t_{i}$ is the type of the $i$-th obstacle.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should be the number of endpoints visible from the $i$-th endpoint.

------  Constraints  ------
$1 ≤ T ≤ 200$
$1 ≤ H ≤ 10^{9}$
$1 ≤ N ≤ 2,000$
$t_{i} \in \{0, 1\}$ for each valid $i$
$1 ≤ x_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ a_{i} ≤ H-1$ for each valid $i$
no two obstacles touch or intersect
the sum of $N$ over all test cases does not exceed $20,000$

----- Sample Input 1 ------ 
1

10 4

0 2 5

1 5 6

1 8 8

0 11 2
----- Sample Output 1 ------ 
2 3 2 3
----- explanation 1 ------ 
Example case 1:

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Mathematics


Solutions:
from collections import *
from bisect import *
from math import *
import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	(h, q) = map(int, input().split())
	r = []
	for i in range(q):
		(tt, x, a) = map(int, input().split())
		r.append([tt, x, a, i])
	r.sort(key=lambda x: x[1])
	fr = [0 for i in range(q)]
	for i in range(q):
		slope1 = float('inf')
		slope2 = -float('inf')
		(x, y) = (r[i][1], r[i][2])
		if r[i][0] == 0:
			typ = 0
		else:
			typ = 1
		c = 0
		for j in range(i + 1, q):
			if typ == 0:
				try:
					cur = (y - r[j][2]) / (x - r[j][1])
				except:
					c += 1
					fr[r[j][3]] += 1
					continue
				if r[j][0] == 1:
					if slope1 > cur and cur > slope2:
						c += 1
						fr[r[j][3]] += 1
					slope1 = min(cur, slope1)
				else:
					if slope2 < cur and cur < slope1:
						c += 1
						fr[r[j][3]] += 1
					slope2 = max(cur, slope2)
			else:
				try:
					cur = (y - r[j][2]) / (x - r[j][1])
				except:
					c += 1
					fr[r[j][3]] += 1
					continue
				if r[j][0] == 1:
					if slope1 > cur and cur > slope2:
						c += 1
						fr[r[j][3]] += 1
					slope1 = min(cur, slope1)
				else:
					if slope2 < cur and cur < slope1:
						c += 1
						fr[r[j][3]] += 1
					slope2 = max(cur, slope2)
			if slope2 >= slope1:
				break
		fr[r[i][3]] += c
	print(*fr)


from sys import stdin
import sys
for _ in range(int(stdin.readline())):
	(h, n) = map(int, stdin.readline().split())
	count = [0] * n
	l = []
	for i in range(n):
		(ti, xi, yi) = map(int, stdin.readline().split())
		l.append([xi, yi, ti, i])
	l = sorted(l, key=lambda x: x[0])
	for i in range(n - 1):
		upper = sys.maxsize
		lower = -upper
		for j in range(i + 1, n):
			if l[i][0] == l[j][0]:
				count[l[j][3]] += 1
				count[l[i][3]] += 1
				continue
			slope = (l[i][1] - l[j][1]) / (l[i][0] - l[j][0])
			if slope > lower and slope < upper:
				count[l[i][3]] += 1
				count[l[j][3]] += 1
			if l[j][2] == 0:
				lower = max(slope, lower)
			elif l[j][2] == 1:
				upper = min(slope, upper)
			if upper < lower:
				break
	for i in count:
		print(i, end=' ')
	print('')


from sys import *
import collections
import math
t = int(stdin.readline())
for _ in range(t):
	(h, n) = list(map(int, stdin.readline().split(' ')))
	ans = [0] * n
	l = []
	for i in range(n):
		(t, x, a) = list(map(int, stdin.readline().split(' ')))
		l.append((x, a, t, i))
	l.sort()
	for i in range(n):
		up = math.inf
		down = -math.inf
		xi = l[i][0]
		ai = l[i][1]
		pi = l[i][3]
		for j in range(i + 1, n, 1):
			xj = l[j][0]
			pj = l[j][3]
			if xj == xi:
				ans[pi] += 1
				ans[pj] += 1
				continue
			aj = l[j][1]
			t = l[j][2]
			s = (aj - ai) / (xj - xi)
			if s > down and s < up:
				ans[pi] += 1
				ans[pj] += 1
			if t == 1:
				up = min(up, s)
			else:
				down = max(down, s)
			if up <= down:
				break
	for h in ans:
		print(h, end=' ')
	print(' ')


from sys import *
import math
import collections
t = int(stdin.readline())
for _ in range(t):
	(h, n) = map(int, stdin.readline().split())
	ans = [0] * n
	l = []
	for i in range(n):
		(t, x, a) = map(int, stdin.readline().split())
		l.append((x, a, t, i))
	l.sort()
	for i in range(n):
		mn = -math.inf
		mx = math.inf
		xi = l[i][0]
		ai = l[i][1]
		fi = l[i][3]
		for j in range(i + 1, n):
			xj = l[j][0]
			fj = l[j][3]
			aj = l[j][1]
			t = l[j][2]
			if xi == xj:
				ans[fi] += 1
				ans[fj] += 1
				continue
			slope = (aj - ai) / (xj - xi)
			if slope > mn and slope < mx:
				ans[fj] += 1
				ans[fi] += 1
			if t == 0:
				mn = max(mn, slope)
			else:
				mx = min(mx, slope)
			if mx <= mn:
				break
	for z in ans:
		print(z, end=' ')
	print()


t = int(input())
for i in range(t):
	(h, n) = [int(i) for i in input().split()]
	ti = []
	for i in range(n):
		(a, b, c) = [int(i) for i in input().split()]
		ti.append((b, c, a, i))
	ti.sort()
	l = [0] * n
	for i in range(n):
		(max_0, min_1) = (float('-inf'), float('inf'))
		for j in range(i + 1, n):
			if ti[j][0] == ti[i][0]:
				l[ti[i][3]] += 1
				l[ti[j][3]] += 1
				continue
			m = (ti[j][1] - ti[i][1]) / (ti[j][0] - ti[i][0])
			if max_0 < m < min_1:
				l[ti[i][3]] += 1
				l[ti[j][3]] += 1
			if ti[j][2] == 1:
				min_1 = min(m, min_1)
			else:
				max_0 = max(m, max_0)
			if max_0 >= min_1:
				break
	print(' '.join([str(i) for i in l]))


from sys import *
import math
try:
	t = int(stdin.readline())
	while t:
		t -= 1
		(h, n) = map(int, stdin.readline().split())
		tower = []
		result = [0] * n
		for i in range(n):
			arr = list(map(int, stdin.readline().split()))
			arr.append(i)
			tower.append(arr)
		tower.sort(key=lambda pair: pair[1])
		for i in range(n):
			up = math.inf
			down = -math.inf
			for j in range(i + 1, n):
				if tower[i][1] == tower[j][1]:
					result[tower[i][3]] += 1
					result[tower[j][3]] += 1
					continue
				slope = (tower[j][2] - tower[i][2]) / (tower[j][1] - tower[i][1])
				if slope < up and slope > down:
					result[tower[i][3]] += 1
					result[tower[j][3]] += 1
				if tower[j][0] == 1:
					up = min(up, slope)
				else:
					down = max(slope, down)
				if up <= down:
					break
		for i in range(len(result)):
			print(result[i], end=' ')
		print(' ')
except:
	pass


import math
for _ in range(int(input())):
	(h, n) = map(int, input().split())
	l = []
	ans = [0] * n
	for i in range(n):
		(t, x, a) = map(int, input().split())
		l.append([x, a, t, i])
	l.sort()
	for i in range(n):
		mx = math.inf
		mn = -math.inf
		xi = l[i][0]
		ai = l[i][1]
		pi = l[i][3]
		for j in range(i + 1, n):
			xj = l[j][0]
			pj = l[j][3]
			aj = l[j][1]
			t = l[j][2]
			if xi == xj:
				ans[pi] += 1
				ans[pj] += 1
				continue
			slope = (aj - ai) / (xj - xi)
			if slope > mn and slope < mx:
				ans[pi] += 1
				ans[pj] += 1
			if t == 1:
				mx = min(mx, slope)
			else:
				mn = max(mn, slope)
			if mx <= mn:
				break
	print(*ans)


from math import inf

def check(greater, lesser):
	if lesser == -inf:
		return True
	if greater == inf:
		return True
	return greater[0] * lesser[1] > lesser[0] * greater[1]
tc = int(input())
while tc > 0:
	(h, n) = map(int, input().split())
	points = []
	for i in range(n):
		(t, x, a) = map(int, input().split())
		points.append((x, a, t, i))
	points.sort()
	ans = [0 for _ in range(n)]
	for i in range(n):
		min_up = inf
		max_down = -inf
		for j in range(i + 1, n):
			if points[j][0] == points[i][0]:
				ans[points[i][3]] += 1
				ans[points[j][3]] += 1
				continue
			cur_slope = (points[j][1] - points[i][1], points[j][0] - points[i][0])
			cur_max = check(cur_slope, max_down)
			cur_min = check(min_up, cur_slope)
			if cur_max and cur_min:
				ans[points[i][3]] += 1
				ans[points[j][3]] += 1
			if not points[j][2]:
				if cur_max:
					max_down = cur_slope
			elif cur_min:
				min_up = cur_slope
			if max_down != -inf and min_up != inf and check(max_down, min_up):
				break
	print(*ans)
	tc -= 1


from math import inf
tc = int(input())
while tc > 0:
	(h, n) = map(int, input().split())
	points = []
	for i in range(n):
		(t, x, a) = map(int, input().split())
		points.append((x, a, t, i))
	points.sort()
	ans = [0 for _ in range(n)]
	for i in range(n):
		min_up = inf
		max_down = -inf
		cur_x = points[i][0]
		cur_y = points[i][1]
		for j in range(i + 1, n):
			if cur_x == points[j][0]:
				ans[points[i][3]] += 1
				ans[points[j][3]] += 1
				continue
			cur_slope = (points[j][1] - cur_y) / (points[j][0] - cur_x)
			cur_min = True if cur_slope < min_up else False
			cur_max = True if cur_slope > max_down else False
			if cur_max and cur_min:
				ans[points[i][3]] += 1
				ans[points[j][3]] += 1
			if not points[j][2]:
				max_down = max(cur_slope, max_down)
			else:
				min_up = min(cur_slope, min_up)
			if min_up <= max_down:
				break
	print(*ans)
	tc -= 1


import math
t = int(input())
for _ in range(t):
	(h, n) = map(int, input().split())
	ans = [0] * n
	l = []
	for __ in range(n):
		(t, x, a) = map(int, input().split())
		l.append((x, a, t, __))
	l.sort()
	for i in range(n):
		up = math.inf
		down = -math.inf
		curr_x = l[i][0]
		curr_height = l[i][1]
		curr_tower_no = l[i][3]
		for j in range(i + 1, n):
			next_x = l[j][0]
			next_height = l[j][1]
			next_tower_no = l[j][3]
			next_tow_type = l[j][2]
			if curr_x == next_x:
				ans[curr_tower_no] += 1
				ans[next_tower_no] += 1
				continue
			s = (next_height - curr_height) / (next_x - curr_x)
			if s > down and s < up:
				ans[curr_tower_no] += 1
				ans[next_tower_no] += 1
			if next_tow_type == 1:
				up = min(up, s)
			else:
				down = max(down, s)
			if up <= down:
				break
	print(*ans)


import math

def get_answer(ans, towers):
	N = len(towers)
	for i in range(N - 1):
		curr_x = towers[i][1]
		curr_a = towers[i][2]
		idx1 = towers[i][3]
		up = math.inf
		down = -math.inf
		for j in range(i + 1, N):
			x = towers[j][1]
			a = towers[j][2]
			typ = towers[j][0]
			idx2 = towers[j][3]
			if curr_x == x:
				ans[idx1] += 1
				ans[idx2] += 1
				continue
			s = (a - curr_a) / (x - curr_x)
			if s < up and s > down:
				ans[idx1] += 1
				ans[idx2] += 1
			if typ == 0:
				if s > down:
					down = s
			elif typ == 1:
				if s < up:
					up = s
			if up <= down:
				break
t = int(input())
while t > 0:
	str = input().split(' ')
	(H, N) = (int(str[0]), int(str[1]))
	towers = []
	for i in range(N):
		str1 = input().split(' ')
		(typ, x, a) = (int(str1[0]), int(str1[1]), int(str1[2]))
		towers.append((typ, x, a, i))
	towers.sort(key=lambda x: x[1])
	ans = [0] * N
	get_answer(ans, towers)
	for i in ans:
		print(i, end=' ')
	print()
	t -= 1


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
mp = lambda : map(int, input().split())
for _ in range(int(input())):
	(h, n) = mp()
	tow = []
	for i in range(n):
		t = ip()
		t = t + [i]
		tow.append(t)
	tow.sort(key=lambda i: i[1])
	ans = [0 for i in range(n)]
	for i in range(n - 1):
		up = float('inf')
		dn = float('-inf')
		(t, x, y, i1) = tow[i]
		for j in range(i + 1, n):
			(tn, xn, yn, i2) = tow[j]
			if x == xn:
				ans[i1] += 1
				ans[i2] += 1
				continue
			slope = (yn - y) / (xn - x)
			if dn < slope and slope < up:
				ans[i1] += 1
				ans[i2] += 1
			if tn == 0:
				dn = max(dn, slope)
			elif tn == 1:
				up = min(up, slope)
			if up <= dn:
				break
	print(*ans)


import math
for k in range(int(input())):
	(height, num) = map(int, input().split())
	temp = []
	tcount = num * [0]
	for i in range(num):
		(stat, x, a) = map(int, input().split())
		temp.append([x, a, stat, i])
	temp.sort()
	for i in range(num):
		ulimit = math.inf
		dlimit = -math.inf
		xi = temp[i][0]
		ai = temp[i][1]
		for j in range(i + 1, num):
			xj = temp[j][0]
			aj = temp[j][1]
			if xi - xj == 0:
				tcount[temp[i][3]] += 1
				tcount[temp[j][3]] += 1
				continue
			tan = (aj - ai) / (xj - xi)
			if tan > dlimit and tan < ulimit:
				tcount[temp[i][3]] += 1
				tcount[temp[j][3]] += 1
			if temp[j][2] == 0:
				dlimit = max(dlimit, tan)
			else:
				ulimit = min(ulimit, tan)
			if dlimit >= ulimit:
				break
	ans = ' '.join((str(x) for x in tcount))
	print(ans)