AtCoder Regular Contest 082 - ConvexScore

You are given N points (x_i,y_i) located on a two-dimensional plane.
Consider a subset S of the N points that forms a convex polygon.
Here, we say a set of points S forms a convex polygon when there exists a convex polygon with a positive area that has the same set of vertices as S. All the interior angles of the polygon must be strictly less than 180°.
For example, in the figure above, {A,C,E} and {B,D,E} form convex polygons; {A,C,D,E}, {A,B,C,E}, {A,B,C}, {D,E} and {} do not.
For a given set S, let n be the number of the points among the N points that are inside the convex hull of S (including the boundary and vertices). Then, we will define the score of S as 2^{n-|S|}.
Compute the scores of all possible sets S that form convex polygons, and find the sum of all those scores.
However, since the sum can be extremely large, print the sum modulo 998244353.

-----Constraints-----
 - 1≤N≤200
 - 0≤x_i,y_i<10^4 (1≤i≤N)
 - If i≠j, x_i≠x_j or y_i≠y_j.
 - x_i and y_i are integers.

-----Input-----
The input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_N y_N

-----Output-----
Print the sum of all the scores modulo 998244353.

-----Sample Input-----
4
0 0
0 1
1 0
1 1

-----Sample Output-----
5

We have five possible sets as S, four sets that form triangles and one set that forms a square. Each of them has a score of 2^0=1, so the answer is 5.

Difficulty: VERY_HARD

Starter code:

Solutions:
from collections import Counter
from fractions import gcd
n = int(input())
xys = [tuple(map(int, input().split())) for _ in range(n)]
MOD = 998244353
excludes = 0
for (i, (x1, y1)) in enumerate(xys):
	slopes = []
	for (x2, y2) in xys[i + 1:]:
		(dx, dy) = (x2 - x1, y2 - y1)
		if dx == 0:
			slopes.append(1j)
		elif dy == 0:
			slopes.append(1)
		else:
			m = gcd(dx, dy)
			slopes.append(dx // m + dy // m * 1j)
	for c in list(Counter(slopes).values()):
		if c > 1:
			excludes += 2 ** c - c - 1
	excludes %= MOD
print((pow(2, n, MOD) - excludes - n * (n - 1) // 2 - n - 1) % MOD)


def main():
	N = int(input())
	points = []
	for i in range(N):
		points.append(list(map(int, input().split())))
	x = [p[0] for p in points]
	y = [p[1] for p in points]
	M = 998244353
	c = 1 + N + N * (N - 1) // 2
	for i in range(N):
		xi = x[i]
		yi = y[i]
		dx = [xj - xi for xj in x]
		dy = [yj - yi for yj in y]
		for j in range(i + 1, N):
			xj = dx[j]
			yj = dy[j]
			cc = 1
			for k in range(j + 1, N):
				if xj * dy[k] - dx[k] * yj == 0:
					cc *= 2
					cc %= M
			c += cc - 1
	r = 1
	for i in range(N):
		r *= 2
		r %= M
	r -= c
	r %= M
	print(r)

def __starting_point():
	main()
__starting_point()


import sys
from collections import defaultdict

def read_int_list():
	return list(map(int, input().split()))

def read_int():
	return int(input())

def read_str_list():
	return input().split()

def read_str():
	return input()

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def solve():

	def collinear(x0, y0, x1, y1):
		return x0 * y1 == x1 * y0

	def aligned(i, j, k):
		return collinear(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i])
	n = read_int()
	mod = 998244353
	res = pow(2, n, mod) - n - 1
	(x, y) = list(zip(*[read_int_list() for i in range(n)]))
	lines = defaultdict(set)
	for i in range(n):
		for j in range(i + 1, n):
			a = y[i] - y[j]
			b = x[j] - x[i]
			g = gcd(a, b)
			a //= g
			b //= g
			if a < 0 or (a == 0 and b < 0):
				(a, b) = (-a, -b)
			c = -(a * x[i] + b * y[i])
			lines[a, b, c].add(i)
			lines[a, b, c].add(j)
	for (k, v) in list(lines.items()):
		m = len(v)
		res -= pow(2, m, mod) - m - 1
	res %= mod
	return res

def main():
	res = solve()
	print(res)

def __starting_point():
	main()
__starting_point()


from collections import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def red(a, b, c):
	if a == 0 and b < 0:
		(b, c) = (-b, -c)
	if a < 0:
		(a, b, c) = (-a, -b, -c)
	g = gcd(a, gcd(abs(b), abs(c)))
	return (a // g, b // g, c // g)

def main():
	md = 998244353
	n = int(input())
	xy = LLI(n)
	cnt_online = {}
	for i in range(n):
		(x0, y0) = xy[i]
		counted = set()
		for j in range(i):
			(x1, y1) = xy[j]
			a = y0 - y1
			b = x1 - x0
			c = -a * x0 - b * y0
			(a, b, c) = red(a, b, c)
			if (a, b, c) in counted:
				continue
			counted.add((a, b, c))
			cnt_online.setdefault((a, b, c), 1)
			cnt_online[a, b, c] += 1
	sum_online = 0
	for plot_n in cnt_online.values():
		sum_online += pow(2, plot_n, md) - 1 - plot_n
		sum_online %= md
	ans = pow(2, n, md) - 1 - n - sum_online
	print(ans % md)
main()


N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
MOD = 998244353
ans = pow(2, N, MOD) - 1 - N
u = set()
for i in range(N):
	(xi, yi) = P[i]
	for j in range(i + 1, N):
		(xj, yj) = P[j]
		if (i, j) in u:
			continue
		cnt = 0
		Q = {i, j}
		for k in range(N):
			(xk, yk) = P[k]
			if (xj - xi) * (yk - yi) == (xk - xi) * (yj - yi):
				cnt += 1
				Q.add(k)
		for p in Q:
			for q in Q:
				u.add((p, q))
		ans -= pow(2, cnt, MOD) - cnt - 1
print(ans % MOD)


import math
mod = 998244353
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
pow2 = [1]
for i in range(n):
	pow2.append(pow2[-1] * 2 % mod)
used = [[False] * n for i in range(n)]
ret = (pow2[n] - 1 - n - n * (n - 1) / 2) % mod
for i in range(n):
	for j in range(i):
		if used[i][j]:
			continue
		inline = [i, j]
		for k in range(n):
			if k == i or k == j:
				continue
			if (p[i][1] - p[k][1]) * (p[j][0] - p[k][0]) == (p[j][1] - p[k][1]) * (p[i][0] - p[k][0]):
				inline.append(k)
		for k in range(len(inline)):
			for l in range(len(inline)):
				used[inline[k]][inline[l]] = True
		v = len(inline)
		ret = (ret + mod - pow2[v] + 1 + v + v * (v - 1) // 2) % mod
print(int(ret))


import sys
input = sys.stdin.readline
from fractions import gcd
from collections import Counter
MOD = 998244353
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
answer = pow(2, N, MOD)
answer -= N + 1
for (i, (x, y)) in enumerate(XY):
	pts = []
	for (x1, y1) in XY[i + 1:]:
		(dx, dy) = (x1 - x, y1 - y)
		g = gcd(dx, dy)
		dx //= g
		dy //= g
		if dx < 0:
			(dx, dy) = (-dx, -dy)
		elif dx == 0:
			dy = 1
		pts.append((dx, dy))
	c = Counter(pts)
	for v in c.values():
		answer -= pow(2, v, MOD) - 1
answer %= MOD
print(answer)


from collections import Counter
N = int(input())
xy_list = [list(map(int, input().split())) for _ in range(N)]
modulo_num = 998244353
duplicate_list = [0] * (N + 1)
for i in range(N):
	(xi, yi) = xy_list[i]
	gradient_list = []
	for j in range(N):
		(xj, yj) = xy_list[j]
		if xi != xj:
			gradient_list.append((yj - yi) / (xj - xi))
		elif yi != yj:
			gradient_list.append(100000)
	counter = Counter(gradient_list)
	for k in counter.values():
		duplicate_list[k + 1] += 1
ans = pow(2, N, modulo_num)
ans -= 1
ans -= N
for i in range(2, N + 1):
	cnt = duplicate_list[i] // i
	ans -= cnt * (pow(2, i, modulo_num) - i - 1)
ans = ans % modulo_num
print(ans)


from collections import Counter
N = int(input())
xy_list = [list(map(int, input().split())) for _ in range(N)]
M = 998244353
res = pow(2, N, M)
res -= 1
res -= N
line_cnt = [0] * (N + 1)
for i in range(N):
	(xi, yi) = xy_list[i]
	angle_list = []
	for j in range(N):
		(xj, yj) = xy_list[j]
		if xj != xi:
			angle_list.append((yj - yi) / (xj - xi))
		elif yj != yi:
			angle_list.append(10000.0)
	cnt_i = Counter(angle_list)
	for k in cnt_i.values():
		line_cnt[k + 1] += 1
for i in range(2, N + 1):
	cnt = line_cnt[i] // i
	res -= cnt * (pow(2, i, M) - i - 1)
res = res % M
print(res)


def main():
	import sys
	input = sys.stdin.readline

	def same_line(p1, p2, p3):
		c1 = complex(p1[0], p1[1])
		c2 = complex(p2[0], p2[1])
		c3 = complex(p3[0], p3[1])
		a = c2 - c1
		b = c3 - c1
		if a.real * b.imag == a.imag * b.real:
			return 1
		else:
			return 0
	mod = 998244353
	N = int(input())
	if N <= 2:
		print(0)
		exit()
	xy = []
	for _ in range(N):
		(x, y) = map(int, input().split())
		xy.append((x, y))
	ans = pow(2, N, mod) - N - 1
	ans %= mod
	used = [[0] * N for _ in range(N)]
	for i in range(N - 1):
		for j in range(i + 1, N):
			if used[i][j]:
				continue
			tmp = [i, j]
			cnt = 2
			for k in range(N):
				if k == i or k == j:
					continue
				if same_line(xy[i], xy[j], xy[k]):
					cnt += 1
					tmp.append(k)
			ans -= pow(2, cnt, mod) - cnt - 1
			ans %= mod
			for a in range(len(tmp)):
				for b in range(a + 1, len(tmp)):
					used[tmp[a]][tmp[b]] = 1
					used[tmp[b]][tmp[a]] = 1
	print(ans % mod)
main()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def inpl():
	return [int(i) for i in input().split()]
from collections import defaultdict
H = defaultdict(lambda : 0)
N = int(input())
dot = [()] * N
mod = 998244353
for i in range(N):
	(x, y) = inpl()
	dot[i] = (x, y)
for i in range(N):
	for j in range(i + 1, N):
		(x1, y1) = dot[i]
		(x2, y2) = dot[j]
		A = y1 - y2
		B = x2 - x1
		C = y1 * x2 - x1 * y2
		if A < 0:
			A *= -1
			B *= -1
			C *= -1
		gcdabc = gcd(gcd(A, B), C)
		A //= gcdabc
		B //= gcdabc
		C //= gcdabc
		H[A, B, C] += 1
ans = (2 ** N - N - 1) % mod
for i in H.values():
	i = int((1 + (1 + 8 * i) ** (1 / 2)) / 2)
	ans -= (2 ** i - i - 1) % mod
print(ans % mod)


from fractions import Fraction
from collections import defaultdict
from itertools import combinations

class Combination:

	def __init__(self, n_max, mod=10 ** 9 + 7):
		self.mod = mod
		self.modinv = self.make_modinv_list(n_max)
		(self.fac, self.facinv) = self.make_factorial_list(n_max)

	def __call__(self, n, r):
		return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

	def make_factorial_list(self, n):
		fac = [1]
		facinv = [1]
		for i in range(1, n + 1):
			fac.append(fac[i - 1] * i % self.mod)
			facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
		return (fac, facinv)

	def make_modinv_list(self, n):
		modinv = [0] * (n + 1)
		modinv[1] = 1
		for i in range(2, n + 1):
			modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
		return modinv
N = int(input())
XY = [list(map(int, input().split())) for i in range(N)]
D = defaultdict(int)
for ((x1, y1), (x2, y2)) in combinations(XY, 2):
	if x1 != x2:
		a = Fraction(y2 - y1, x2 - x1)
		b = Fraction(y1) - a * Fraction(x1)
		D[a, b] += 1
	else:
		D[None, x1] += 1
mod = 998244353
comb = Combination(N + 1, mod)
A = [0] * (N + 1)
coA = [0] * (N + 1)
ans = 0
for i in range(3, N + 1):
	ans += comb(N, i)
	ans %= mod
for i in range(3, N + 1):
	for j in range(i - 2):
		A[i] += (i - 2 - j) * (1 << j)
	coA[i] = coA[i - 1] + A[i]
for ((a, b), n) in D.items():
	if n == 1:
		continue
	n = int((n << 1) ** 0.5) + 1
	ans -= coA[n]
	ans %= mod
print(ans)