Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Problem B
  Parallel Lines

  Given an even number of distinct planar points, consider coupling all of the points into pairs. All the possible couplings are to be considered as long as all the given points are coupled to one and only one other point.

  When lines are drawn connecting the two points of all the coupled point pairs, some of the drawn lines can be parallel to some others. Your task is to find the maximum number of parallel line pairs considering all the possible couplings of the points.

  For the case given in the first sample input with four points, there are three patterns of point couplings as shown in Figure B.1. The numbers of parallel line pairs are 0, 0, and 1, from the left. So the maximum is 1.

Figure B.1. All three possible couplings for Sample Input 1

  For the case given in the second sample input with eight points, the points can be coupled as shown in Figure B.2. With such a point pairing, all four lines are parallel to one another. In other words, the six line pairs $(L_1, L_2)$, $(L_1, L_3)$, $(L_1, L_4)$, $(L_2, L_3)$, $(L_2, L_4)$ and $(L_3, L_4)$ are parallel. So the maximum number of parallel line pairs, in this case, is 6.

Input

  The input consists of a single test case of the following format.

$m$
$x_1$ $y_1$
...
$x_m$ $y_m$

  Figure B.2. Maximizing the number of parallel line pairs for Sample Input 2

  The first line contains an even integer $m$, which is the number of points ($2 \leq m \leq 16$). Each of the following $m$ lines gives the coordinates of a point. Integers $x_i$ and $y_i$ ($-1000 \leq x_i \leq 1000, -1000 \leq y_i \leq 1000$) in the $i$-th line of them give the $x$- and $y$-coordinates, respectively, of the $i$-th point.

  The positions of points are all different, that is, $x_i \ne x_j$ or $y_i \ne y_j$ holds for all $i  \ne j$. Furthermore, No three points lie on a single line.

Output

  Output the maximum possible number of parallel line pairs stated above, in one line.

Sample Input 1

4
0 0
1 1
0 2
2 4

Sample Output 1

1

Sample Input 2

8
0 0
0 5
2 2
2 7
3 -2
5 0
4 -2
8 2

Sample Output 2

6

Sample Input 3

6
0 0
0 5
3 -2
3 5
5 0
5 7

Sample Output 3

3

Sample Input 4

2
-1000 1000
1000 -1000

Sample Output 4

0

Sample Input 5

16
327 449
-509 761
-553 515
360 948
147 877
-694 468
241 320
463 -753
-206 -991
473 -738
-156 -916
-215 54
-112 -476
-452 780
-18 -335
-146 77

Sample Output 5

12



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


Sample output:
1

Submission status: Accepted

Solution code:
m = int(input())
P = [list(map(int, input().split())) for i in range(m)]
s = set()
for i in range(m):
    xi, yi = P[i]
    for j in range(i+1, m):
        xj, yj = P[j]
        u = xj - xi; v = yj - yi
        for x, y in s:
            if x * v == y * u:
                break
        else:
            s.add((u, v))
memo = {}
def dfs(state, dx, dy):
    if (state, dx, dy) in memo:
        return memo[state, dx, dy]
    pstate = state
    update = 1
    cnt = -1
    while update:
        update = 0; cnt += 1
        for i in range(m):
            if (state >> i) & 1:
                continue
            xi, yi = P[i]
            for j in range(i+1, m):
                if (state >> j) & 1:
                    continue
                xj, yj = P[j]
                u = xj - xi; v = yj - yi
                if dx * v == dy * u:
                    update = 1
                    state |= (1 << i) | (1 << j)
                    break
            if update: break
    if cnt <= 1:
        res = 0
    else:
        res = cnt*(cnt-1)//2 + max(dfs(state, *e) for e in s)
    memo[pstate, dx, dy] = res
    return res
print(max(dfs(0, *e) for e in s))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from fractions import Fraction
import os
import sys


def main():
    M = read_int()
    A = [Vec(*read_ints()) for _ in range(M)]
    print(solve(M, A))


def solve(M, A):
    D = [[None] * M for _ in range(M)]
    last_did = 0
    did_map = {}
    for i in range(M):
        for j in range(i + 1, M):
            v = A[j] - A[i]
            if v.y < 0 or (v.y == 0 and v.x < 0):
                v = -v
            c = Fraction(v.x ** 2, v.abs2())
            if v.x < 0:
                c = -c
            if c not in did_map:
                did_map[c] = last_did
                did = last_did
                last_did += 1
            else:
                did = did_map[c]
            D[i][j] = did
            D[j][i] = did

    used = [False] * M
    m = {}
    best = 0

    def rec(i):
        nonlocal best
        while i < M and used[i]:
            i += 1
        if i == M:
            s = 0
            for c in m.values():
                s += c * (c - 1) // 2
            best = max(best, s)
            return

        used[i] = True
        for j in range(i + 1, M):
            if used[j]:
                continue
            used[j] = True
            d = D[i][j]
            if d not in m:
                m[d] = 1
            else:
                m[d] += 1
            rec(i + 1)
            m[d] -= 1
            if m[d] == 0:
                del m[d]
            used[j] = False
        used[i] = False

    rec(0)
    return best


###############################################################################

class Vec(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
        super().__init__()

    def __add__(self, other):
        return Vec(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vec(self.x - other.x, self.y - other.y)

    def __mul__(self, scalar):
        return Vec(self.x * scalar, self.y * scalar)

    def __rmul__(self, scalar):
        return Vec(self.x * scalar, self.y * scalar)

    def __truediv__(self, scalar):
        return Vec(self.x / scalar, self.y / scalar)

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self

    def __isub__(self, other):
        self.x -= other.x
        self.y -= other.y
        return self

    def __imul__(self, scalar):
        self.x *= scalar
        self.y *= scalar
        return self

    def __idiv__(self, scalar):
        self.x /= scalar
        self.y /= scalar
        return self

    def __neg__(self):
        return Vec(-self.x, -self.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __ne__(self, other):
        return not self.__eq__(other)

    def __hash__(self):
        return hash(('Vec', self.x, self.y))

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def abs2(self):
        return self.x * self.x + self.y * self.y

    def __abs__(self):
        return math.sqrt(float(self.abs2()))

    def __repr__(self):
        return '({}, {})'.format(self.x, self.y)


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    ans = 0
    for l in range(1,n+1):
        for i in range(1000):
            if i*k > l:break
            j = l-i*k+i
            if j%2:
                j //= 2
                j += 1
                s = 1
                for a in range(i):
                    s *= j-a
                    s //= a+1
                ans += s
    print(ans)
    return


def dfs(d,k,f,n,nu,v,e):
    global ans
    if d == nu:
        l = defaultdict(int)
        for i in k:
            l[i] += 1
        res = 0
        for i in l.values():
            res += calc(i)
        if res > ans:
            ans = res
    else:
        for i in range(n):
            if f[i]:
                p = i
                break
        f_ = [f[i] if i != p else 0 for i in range(n)]
        for q in range(p+1,n):
            if f[q]:
                m = e[(p,q)]
                k_ = [k[i] if i != d else m for i in range(nu)]
                f__ = [f_[i] if i != q else 0 for i in range(n)]
                dfs(d+1,k_,f__,n,nu,v,e)

def calc(n):
    return n*(n-1)//2

def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
ans = 0
#B
def B():
    n = I()
    nu = n//2
    v = LIR(n)
    v.sort()
    e = defaultdict(set)
    for p in range(n):
        for q in range(p+1,n):
            x,y = v[q][0]-v[p][0],v[q][1]-v[p][1]
            if x == 0:
                if y < 0:
                    m = (0,-1)
                else:
                    m = (0,1)
            elif y == 0:
                m = (1,0)
            else:
                g = gcd(x,abs(y))
                m = (x//g,y//g)
            e[(p,q)] = m
    f = [1 for i in range(n)]
    k = [None for i in range(n//2)]
    dfs(0,k,f,n,nu,v,e)
    print(ans)
    return


#C
def C():
    while 1:
        n = I()
        if n == 0:
            break
        v = [input().split() for i in range(n)]
        d = defaultdict(int)
        f = [[1 for j in range(n)] for i in range(n)]
        i = 0
        s = 0
        while i < n:
            v[i][1] = int(v[i][1])
            v[i][2] = int(v[i][2])
            if v[i][2] == 0:
                s += v[i][1]
                v.pop(i)
                n -= 1
            else:
                d[v[i][0]] = i
                i += 1

        for i in range(n):
            for j in v[i][3:]:
                f[i][d[j]] = 0
        e = [[] for i in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j:continue
                if f[i][j]:
                    e[i].append(j)
        for i in e:
            print(i)
        print(ans)
    return

#D
def D():
    n = I()
    s = [0 for i in range(100001)]
    l = LIR(n)
    l.sort(key = lambda x:x[1])
    r = [l[i][0] for i in range(n)]
    r.sort()
    f = [0 for i in range(100001)]
    for a,b in l:
        s[a] += 1
        s[b] -= 1
        f[b] += 1
    for i in range(100000):
        s[i+1] += s[i]
        f[i+1] += f[i]
    ans = 0

    for a,b in l:
        ri = bisect.bisect_left(r,b)
        ri = n-ri
        le = f[a]
        ans = max(ans,n-(ri+le))
    print(ans,max(s))
    return

#E
def E():
    n = I()
    c = LI()
    f = [[i,c[i]] for i in range(n)]
    f.sort(key = lambda x:x[1])
    v = [[] for i in range(n)]
    m = I()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque()
    bfs_map = [1 for i in range(n)]
    ans = [0 for i in range(n)]
    for i,j in f:
        if not bfs_map[i]:continue
        q.append(i,-1)
        bfs_map[i] = 0
        ans[i] = 1
        while q:
            x,pre = q.popleft()
            for y in v[x]:
                if bfs_map[y]:
                    if x == 0:
                        bfs_map[y] = 0
                        q.append(y)
    print(sum(ans))
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
from fractions import gcd
m = int(input())
P = [list(map(int, input().split())) for _ in range(m)]
tmp = {}
for i, pi in enumerate(P):
    for j, pj in enumerate(P):
        if i == j:
            break
        x = pi[0] - pj[0]
        y = pi[1] - pj[1]
        k = (x / gcd(x, y), y / gcd(x, y))
        if k in tmp:
            tmp[k].append([pi, pj])
        else:
            tmp[k] = [[pi, pj]]

dic = {}
for t in tmp:
    if len(tmp[t]) == 1:
        continue
    dic[t] = tmp[t]

ans = 0 
for d1 in dic:
    line1 = []
    line1.append(dic[d1])
    used1 = [p for pp in dic[d1] for p in pp]
    for d2 in dic:
        tmp = []
        for t in dic[d2]:
            if t[0] in used1 or t[1] in used1:
                continue
            tmp.append(t)
        if 1 == len(tmp):
            continue
        line2 = line1 + [tmp]
        used2 = used1 + [p for pp in tmp for p in pp]

        for d3 in dic:
            tmp = []
            for t in dic[d3]:
                if t[0] in used2 or t[1] in used2:
                    continue
                tmp.append(t)
            if 1 == len(tmp):
                continue
            line3 = line2 + [tmp]
            used3 = used2 + [p for pp in tmp for p in pp]

            for d4 in dic:
                tmp = []
                for t in dic[d4]:
                    if t[0] in used3 or t[1] in used3:
                        continue
                    tmp.append(t)
                    if 1 == len(tmp):
                        continue
                line4 = line3 + [tmp]
                anstmp = 0
                for l in line4:
                    anstmp += len(l) * (len(l) - 1) / 2
                ans = max(anstmp, ans)
print(int(ans))