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: Runtime Error

Solution code:
import math
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'arc082-e.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N = int(lines[0])
            for i in range(N):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N = int(lines[0])
        for i in range(N):
            lines.append(input())

    return lines

def isIncluded(ref_points, ref):
    min_y = ref_points[0]['y']
    min_index = 0
    for i in range(1, len(ref_points)):
        if(min_y > ref_points[i]['y']):
            min_y = ref_points[i]['y']
            min_index = i

    points = []
    p = {}
    for i in range(len(ref_points)):
        data = {}
        data['x'] = ref_points[i]['x'] - ref_points[min_index]['x']
        data['y'] = ref_points[i]['y'] - ref_points[min_index]['y']
        data['rad'] = math.atan2(data['y'], data['x'])
        points.append(data)

    p['x'] = ref['x'] - ref_points[min_index]['x']
    p['y'] = ref['y'] - ref_points[min_index]['y']

    points = sorted(points, key=lambda x: x['rad'])

    lines = []
    v1 = {}
    v2 = {}
    Included = True

    lines = ((0,1), (1,2), (2,0))

    for n in range(3):
        v1['x'] = points[lines[n][1]]['x']   - points[lines[n][0]]['x']
        v1['y'] = points[lines[n][1]]['y']   - points[lines[n][0]]['y']
        v2['x'] = p['x'] - points[lines[n][1]]['x']
        v2['y'] = p['y'] - points[lines[n][1]]['y']

        cross = v1['x']*v2['y'] - v2['x']*v1['y']
        # print(v1, v2)
        # print(cross)
        if(cross < 0):
            return False

    if(Included):
        return True
    else:
        return False


def isConvex(xy, points):
    lines = []
    v1 = {}
    v2 = {}
    N = len(points)

    for n in range(N-1):
        lines.append((points[n], points[n+1]))
    lines.append((points[n+1], points[0]))
    lines.append(lines[0])

    for n in range(N):
        v1['x'] = xy[lines[n][1]]['x']   - xy[lines[n][0]]['x']
        v1['y'] = xy[lines[n][1]]['y']   - xy[lines[n][0]]['y']
        v2['x'] = xy[lines[n+1][1]]['x'] - xy[lines[n+1][0]]['x']
        v2['y'] = xy[lines[n+1][1]]['y'] - xy[lines[n+1][0]]['y']

        cross = v1['x']*v2['y'] - v2['x']*v1['y']
        if(cross <= 0):
            return False

    return True


def sort_by_rad(xy, points):
    min_y = xy[points[0]]['y']
    min_index = 0
    for i in range(1, len(points)):
        if(min_y > xy[points[i]]['y']):
            min_y = xy[points[i]]['y']
            min_index = i

    new_points = []
    for i in range(len(points)):
        data = {}
        data['x'] = xy[points[i]]['x'] - xy[points[min_index]]['x']
        data['y'] = xy[points[i]]['y'] - xy[points[min_index]]['y']
        data['rad'] = math.atan2(data['y'], data['x'])
        data['index'] = points[i]
        new_points.append(data)

    sort_points = sorted(new_points, key=lambda x: x['rad'])
    results = []
    for i in range(len(points)):
        results.append(sort_points[i]['index'])

    return results


def E_ConvexScore():
    raw_data = read_data()

    xy = []
    N = int(raw_data[0])
    key_list = ["x", "y"]
    min_xy = dict(zip(key_list, list(map(int, raw_data[1].split()))))
    max_xy = dict(zip(key_list, list(map(int, raw_data[1].split()))))
    index_min = 0

    for i in range(N):
        xy.append(dict(zip(key_list, list(map(int, raw_data[i+1].split())))))
        xy[i]['rad'] = math.atan2(xy[i]['y'], xy[i]['x'])
        xy[i]['d'] = xy[i]['y'] + xy[i]['x']

    xy_d = sorted(xy, key=lambda x: x['d'])
    xy_rad = sorted(xy_d, key=lambda x: x['rad'])
    xy = xy_rad

    included = {}
    total_rank = 0
    for points in itertools.combinations(range(N), 3):
        new_points = sort_by_rad(xy, points)
        # print(new_points)
        if(not isConvex(xy, new_points)):
            included[points] = set([])
            continue
        count = 0
        index_included = []
        for i in range(points[0]+1, points[2]):
            if(i in points):
                continue
            elif(isIncluded(list([xy[points[0]], xy[points[1]], xy[points[2]]]), xy[i])):
                count += 1
                index_included.append(i)
        included[points] = set(index_included)
        # print(count)
        total_rank += pow(2, count)

    # print(included)

    for i in range(4, N+1):
        for points in itertools.combinations(range(N), i):
            new_points = sort_by_rad(xy, points)

            if(not isConvex(xy, new_points)):
                continue

            # print(new_points)
            count_set = set([])
            for j in range(i-2):
                triangle = (new_points[0], new_points[j+1], new_points[j+2])
                count_set = count_set ^ included[triangle]

            # print(count_set)
            total_rank += pow(2, len(count_set))

    print(total_rank)

E_ConvexScore()

Submission status: Runtime Error

Solution code:
from collections import Counter
from math 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: Runtime Error

Solution code:
4
0 0
0 1
1 0
1 1

Submission status: Runtime Error

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 != xj:
            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)