Problem:


Score : 700 points

Problem Statement

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 1

4
0 0
0 1
1 0
1 1

Sample Output 1

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.

Sample Input 2

5
0 0
0 1
0 2
0 3
1 1

Sample Output 2

11

We have three "triangles" with a score of 1 each, two "triangles" with a score of 2 each, and one "triangle" with a score of 4. Thus, the answer is 11.

Sample Input 3

1
3141 2718

Sample Output 3

0

There are no possible set as S, so the answer is 0.



Sample input:
4
0 0
0 1
1 0
1 1


Sample output:
5

Submission status: Wrong Answer

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

    def same_line(p1, p2, p3):
        eps = 10**-8
        c1 = complex(p1[0], p1[1])
        c2 = complex(p2[0], p2[1])
        c3 = complex(p3[0], p3[1])
        d = (c2-c1) / (c3-c1)
        if abs(d.imag) < eps:
            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)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    def same_line(p1, p2, p3):
        eps = 10**-8
        c1 = complex(p1[0], p1[1])
        c2 = complex(p2[0], p2[1])
        c3 = complex(p3[0], p3[1])
        d = (c2-c1) / (c3-c1)
        if abs(d.imag) < eps:
            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
    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)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    def same_line(p1, p2, p3):
        eps = 10**-8
        c1 = complex(p1[0], p1[1])
        c2 = complex(p2[0], p2[1])
        c3 = complex(p3[0], p3[1])
        d = (c2-c1) / (c3-c1)
        if abs(d.imag) < eps:
            return 1
        else:
            return 0

    mod = 998244353
    N = int(input())

    if N <= 2:
        print(0)

    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    ans = pow(2, N, mod) - N - 1
    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)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    def same_line(p1, p2, p3):
        eps = 10**-8
        c1 = complex(p1[0], p1[1])
        c2 = complex(p2[0], p2[1])
        c3 = complex(p3[0], p3[1])
        d = (c2-c1) / (c3-c1)
        if abs(d.imag) < eps:
            return 1
        else:
            return 0

    mod = 998244353
    N = int(input())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    ans = pow(2, N, mod) - N - 1
    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)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    def same_line(p1, p2, p3):
        eps = 10**-8
        c1 = complex(p1[0], p1[1])
        c2 = complex(p2[0], p2[1])
        c3 = complex(p3[0], p3[1])
        d = (c2-c1) / (c3-c1)
        if abs(d.imag) < eps:
            return 1
        else:
            return 0

    mod = 998244353
    N = int(input())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    ans = pow(2, N, mod) - N - 1
    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)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    def same_line(p1, p2, p3):
        eps = 10**-8
        c1 = complex(p1[0], p1[1])
        c2 = complex(p2[0], p2[1])
        c3 = complex(p3[0], p3[1])
        d = (c2-c1) / (c3-c1)
        if abs(d.imag) < eps:
            return 1
        else:
            return 0

    mod = 998244353
    N = int(input())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    ans = pow(2, N, mod) - N - 1
    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
            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)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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

print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

M = 998244353
N = 0
points = []

def calc(s, ap, dp):
    global M, N, points

    r = 0
    s0, si = s[0], s[-1]
    x0, y0 = points[s0]
    xi, yi = points[si]
    for j in ap:
        if j < s0:
            continue
        sc = s.copy()
        sc.append(j)
        xj, yj = points[j]
        apc = []
        dpc = dp

        for k in ap:
            if k == j:
                continue
            xk, yk = points[k]
            o1 = (xj - xi) * (yk - yi) - (xk - xi) * (yj - yi)
            if o1 < 0:
                continue
            o2 = (x0 - xj) * (yk - yj) - (xk - xj) * (y0 - yj)
            if o2 < 0:
                apc.append(k)
            else:
                dpc += 1

        r += 2 ** dpc
        r %= M
        if 0 < len(apc):
            r += calc(sc, apc, dpc)
            r %= M

    return r


def main():
    global M, N, points

    N = int(input())
    for i in range(N):
        points.append(list(map(int, input().split())))

    r = 0
    for i in range(N):
        xi, yi = points[i]
        for j in range(i + 1, N):
            xj, yj = points[j]
            s = [i, j]
            ap = []
            for k in range(N):
                if k == i or k == j:
                    continue
                xk, yk = points[k]
                if 0 < (xj - xi) * (yk - yi) - (xk - xi) * (yj - yi):
                    ap.append(k)
            r += calc(s, ap, 0)
            r %= M

    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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
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
        if A < 0:
            A *= -1
            B *= -1
            C *= -1
        H[(A, B, C)] += 1
ans = 2**N - N - 1
for i in H.values():
    i = int((1+(1+8*i)**(1/2))/2)
    ans -= 2**i - i - 1
print(ans)

Submission status: Wrong Answer

Solution code:
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
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
for i in H.values():
    i = int((1+(1.1+8*i)**(1/2))/2)
    ans -= 2**i - i - 1
print(ans)

Submission status: Wrong Answer

Solution code:
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
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
for i in H.values():
    i = int((1+(1+8*i)**(1/2))/2)
    ans -= 2**i - i - 1
print(ans)

Submission status: Wrong Answer

Solution code:
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
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
for i in H.values():
    i = int((1+(1+8*(i+10**(-5)))**(1/2))/2)
    ans -= 2**i - i - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from fractions import Fraction
mod = 998244353
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
pow2 = [2**i % mod for i in range(n + 1)]
dic = {}
for i in range(n):
    for j in range(i):
        a = (p[i][1] - p[j][1]) / (p[i][0] - p[j]
                                       [0]) if p[i][0] != p[j][0] else 10**9
        b = p[i][1] - p[i][0] * a if p[i][0] != p[j][0] else p[i][0]
        if (a, b) in dic:
            dic[(a, b)] += 1
        else:
            dic[(a, b)] = 1
ret = (pow2[n] - 1 - n - n * (n - 1) / 2)
for v in dic.values():
    x = int((math.sqrt(8 * v + 1) + 1) / 2)
    ret = (ret + mod - pow2[x] + 1 + x + x * (x - 1) // 2) % mod
print(int(ret))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
dat = [list(map(int, input().split())) for i in range(n)]
dic = {}
mod = 998244353
mp = [(2**i) % mod for i in range(n + 1)]
ret = (mp[n] - 1 - n * (n + 1) / 2) % mod
for i in range(n):
    for j in range(i):
        a = 0
        b = 0
        if dat[i][0] == dat[j][0]:
            a = 10**9
            b = dat[i][0]
        else:
            a = (dat[i][1] - dat[j][1]) / (dat[i][0] - dat[j][0])
            b = dat[i][1] - dat[i][0] * a
        if (a, b) in dic:
            dic[(a, b)] += 1
        else:
            dic[(a, b)] = 1
for v in dic.values():
    x = int((math.sqrt(8 * v + 1) + 1) / 2)
    ret = (ret + mod - mp[x] + 1 + x * (x + 1) / 2) % mod
print(int(ret))

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import Fraction
mod = 998244353
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
pow2 = [2**i % mod for i in range(n + 1)]
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))

Submission status: Time Limit Exceeded

Solution code:
import sys

# 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 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 = zip(*[read_int_list() for i in range(n)])
    done = set()
    for i in range(n):
        for j in range(i + 1, n):
            if (i, j) not in done:
                line = [i, j]
                for k in range(n):
                    if k not in [i, j]:
                        if aligned(i, j, k):
                            line.append(k)

                for u in line:
                    for v in line:
                        if u != v:

                            done.add((u, v))
                m = len(line)
                res -= pow(2, m, mod) - m - 1
    res %= mod
    return res


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# E
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
for i in range(N):
    xi, yi = xy_list[i]
    for j in range(i+1, N):
        xj, yj = xy_list[j]
        # count points in same line
        cnt = 0
        valid = 1
        for k in range(N):
            xk, yk = xy_list[k]
            if ((xk-xi)*(xk-xj) + (yk-yi)*(yk-yj))**2 == ((xk-xi)**2 + (yk-yi)**2)*((xk-xj)**2 + (yk-yj)**2):
                if k < j and k != i:
                    valid = 0
                else:
                    cnt += 1
        if cnt > 0 and valid == 1:
            # print(i, j, cnt)
            res -= (pow(2, cnt, M)-cnt-1)

res = res % M
print(res)

Submission status: Accepted

Solution code:
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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# 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)

Submission status: Accepted

Solution code:
from collections import Counter

if __name__ == '__main__':
    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)

Submission status: Accepted

Solution code:
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 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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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 = 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 lines.items():
        m = len(v)
        res -= pow(2, m, mod) - m - 1
    res %= mod
    return res


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 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)