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: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from fractions import gcd
from collections import Counter

"""
適当に部分集合Xをとり、凸包 S として、Sに1点計上すればよい
これだと2^N点得られる
ただし、凸包の面積が0となる場合が例外
空集合、1点の場合と、線分の場合を除外する

"""

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# 空、1点
for i,(x,y) in enumerate(XY):
    # i を選び、i+1番目以上のうちいくつかを選んで線分とする
    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)

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)))


#!/usr/bin/env python3


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()

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 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 collections import Counter

def __starting_point():
    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 list(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)

__starting_point()

# seishin.py
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)

from fractions import Fraction
from collections import defaultdict
from itertools import combinations
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    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):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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)

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 = {}
    # 各２点を結ぶ直線をax+by+c=0の(a,b,c)で表し
    # 各直線上にいくつの点があるかカウントする
    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
    # print(cnt_online)
    # 各直線上で、2点以上で多角形ができない点の選び方を数える
    sum_online = 0
    for plot_n in cnt_online.values():
        sum_online += pow(2, plot_n, md) - 1 - plot_n
        sum_online %= md
    # すべての2点以上の選び方から、多角形ができないものを引く
    ans = pow(2, n, md) - 1 - n - sum_online
    print(ans % md)

main()


# E
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)
# 0 points
res -= 1
# 1 points
res -= N

# all lines
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)
        
    # count points in same line
    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)

import sys
from collections import defaultdict

# sys.stdin = open('e1.in')


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()