Problem:


秋のイルミネーション

 四角形が大好きな人が多く住む四角町では、四角形の電光板を組み合わせたイルミネーションで町中を彩るお祭りが開催されます。この電光板は電気を流すと発光し、発光している板に接している板も発光します。したがって、電光板を何枚使っても、すべてがひとかたまりに接していれば電源がひとつで済むという優れものです。
 

お祭り実行委員会では、四角形を組み合わせたデザインを町民から募集し多数のイルミネーションを作成します。各イルミネーションは、デザインを構成する四角形の配置によって必要となる電源の個数が変わるため、必要な電源の個数を把握する作業に大きな手間がかかります。そこで、あなたは四角形の配置を調べ、必要な電源の個数を計算するプログラムを作成して実行委員会を手助けすることにしました。

イルミネーションの個数、各イルミネーションを構成する四角形の情報を入力とし、イルミネーションごとに必要な電源の個数を出力するプログラムを作成してください。重なっていたり接していたりする四角形を 1 つのまとまりと考え、1 つのまとまりに対して電源の個数は 1 つと数えてください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

N
M1
xa1 ya1 xb1 yb1 xc1 yc1 xd1 yd1
xa2 ya2 xb2 yb2 xc2 yc2 xd2 yd2
:
xaM1 yaM1 xbM1 ybM1 xcM1 ycM1 xdM1 ydM1
M2
:
:
MN
:
:

1 行目にイルミネーションの個数 N (1 ≤ N ≤ 100) が与えられます。続いて、N 個のイルミネーションの情報が与えられます。第 i のイルミネーションの情報として、イルミネーションを構成する四角形の個数 Mi (1 ≤ Mi ≤ 100) が１行に与えられます。続く Mi 行に j 個目の四角形の頂点 xaj, yaj, xbj, ybj, xcj, ycj, xdj, ydj (-1000 以上 1000 以下の整数) が与えられます。

入力される四角形の頂点座標は、時計回りの順に従って入力されます。ただし、入力データの四角形はすべて凸な四角形とします。

  

データセットの数は 10 を超えません。

Output

入力データセットごとに、イルミネーションごとに必要な電源の個数を出力します。出力する電源の個数は各イルミネーションが入力された順番に従ってください。

Sample Input

3
1
0 0 0 1 1 1 1 0
2
0 0 0 1 1 1 1 0
100 100 100 200 200 200 200 100
2
0 0 0 100 100 100 100 0
10 10 10 20 20 20 20 10
2
1
30 40 40 50 40 20 20 10
1
30 40 40 50 40 20 20 10
0

Output for the Sample Input

1
2
1
1
1



Sample input:
3
1
0 0 0 1 1 1 1 0
2
0 0 0 1 1 1 1 0
100 100 100 200 200 200 200 100
2
0 0 0 100 100 100 100 0
10 10 10 20 20 20 20 10
2
1
30 40 40 50 40 20 20 10
1
30 40 40 50 40 20 20 10
0


Sample output:
1
2
1
1
1

Submission status: Wrong Answer

Solution code:
while(True):
    try:
        n = input()
    except:
        break

Submission status: Wrong Answer

Solution code:
while(True):
    try:
        n = int(input())
        for _ in range(n):
            m = int(input())
            xys = [ map(int,input().split()) for i in range(m) ]
            print(1)
    except:
        break

Submission status: Wrong Answer

Solution code:
exit()

Submission status: Wrong Answer

Solution code:
from sys import stdin
while(True):
    try:
        n = int(stdin.readline())
    except:
        break
    if not n: break
    for _ in range(n):
        try: m = int(stdin.readline())
        except: break
        hoge = [list(map(int, stdin.readline().split())) for j in range(m)]
        print("1")

Submission status: Wrong Answer

Solution code:
from sys import stdin
stdin.readline()
stdin.readline()
while(True):
    try:
        n = int(stdin.readline())
    except:
        break
    if not n: break
    for _ in range(n):
        m = int(stdin.readline())
        try: hoge = [list(map(int, stdin.readline().split())) for j in range(m)]
        except: excit()
        print("1")

Submission status: Wrong Answer

Solution code:
from sys import stdin
while(True):
    try:
        n = int(stdin.readline())
    except:
        break
    if not n: break
    for _ in range(n):
        try: m = int(stdin.readline())
        except: exit()
        hoge = [list(map(int, stdin.readline().split())) for j in range(m)]
        print("1")

Submission status: Wrong Answer

Solution code:
from sys import stdin
while(True):
    try:
        n = int(stdin.readline())
    except:
        break
    if not n: break
    for _ in range(n):
        try: m = int(stdin.readline())
        except: exit()
        hoge = [list(map(int, stdin.readline().split())) for j in range(m)]
        print("1\n")

Submission status: Wrong Answer

Solution code:
from sys import stdin
while(True):
    try:
        n = int(stdin.readline())
    except:
        exit()
    if not n: exit()
    for _ in range(n):
        try: m = int(stdin.readline())
        except: exit()
        hoge = [list(map(int, stdin.readline().split())) for j in range(m)]
        print("1\n")

Submission status: Accepted

Solution code:
def dot3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
    ax, ay = A; bx, by = B
    return (ax - bx) ** 2 + (ay - by) ** 2
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    if C0 == C1 == 0:
        E0 = dot3(P0, P1, Q0)
        E1 = dot3(P0, P1, Q1)
        if not E0 < E1:
            E0, E1 = E1, E0
        return E0 <= dist2(P0, P1) and 0 <= E1
    return C0 * C1 <= 0 and D0 * D1 <= 0

def contains(P, Q):
    v = []
    for q in Q:
        for i in range(4):
            v.append(cross3(P[i-1], P[i], q))
        if all(e <= 0 for e in v) or all(e >= 0 for e in v):
            return 1
    return 0

def check(Pi, Pj):
    if contains(Pi, Pj) or contains(Pj, Pi):
        return 1
    for i in range(4):
        for j in range(4):
            if is_intersection(Pi[i-1], Pi[i], Pj[j-1], Pj[j]):
                return 1
    return 0

def solve():
    M = readline(1)[0]
    *p, = range(M)
    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y
    def unite(x, y):
        px = root(x); py = root(y)
        if px < py:
            p[py] = px
        else:
            p[px] = py

    P = []
    for i in range(M):
        xa, ya, xb, yb, xc, yc, xd, yd = readline(8)
        P.append(((xa, ya), (xb, yb), (xc, yc), (xd, yd)))
    for i in range(M):
        for j in range(i+1, M):
            if check(P[i], P[j]):
                unite(i, j)
    res = 0
    for i in range(M):
        if i == root(i):
            res += 1
    return res


*r, = map(int, open(0).read().split())
it = iter(r)

def readline(v):
    r = []
    for i in range(v):
        r.append(next(it))
    return r

while 1:
    N = readline(1)[0]
    if N == 0:
        break
    for i in range(N):
        print(solve())

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
        b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
        if a > b: return False
    else:
        return True

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False
while(True):
    n = int(stdin.readline())
    if not n: break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for __ in range(m) ]
        for i in range(m):
            for j in range(i+1,m):
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
        b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
        if a > b: return False
    else:
        return True

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for __ in range(m) ]
        for i in range(m):
            for j in range(i+1,m):
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    for i in range(4):
        chk = True
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk = False; break
        if chk: return True
    else:
        return False

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for __ in range(m) ]
        for i in range(m):
            for j in range(i+1,m):
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    for i in range(4):
        chk = True
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk = False; break
        if chk: return True
    else:
        return False

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for i in range(m) ]
        for i in range(m):
            for j in range(i+1,m):
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    for i in range(4):
        chk = True
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk = False; break
        if chk: return True
    else:
        return False

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for i in range(m) ]
        for i in range(m):
            if len(set(p)) == 1: print(1); break
            for j in range(i+1,m):
                if p[i] == p[j]:
                    continue
                if chk_in_rect(xys[i],xys[j]):
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    p = [i if e==j else e for e in p]
                    continue
        else: print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    for i in range(4):
        chk = True
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk = False; break
        if chk: return True
    else:
        return False

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(float, stdin.readline().split())) for i in range(m) ]
        for i in range(m):
            if len(set(p)) == 1: print(1); break
            for j in range(i+1,m):
                if p[i] == p[j]:
                    continue
                if chk_in_rect(xys[i],xys[j]):
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    p = [i if e==j else e for e in p]
                    continue
        else: print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    chk = True
    for i in range(4):
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk = False; break
    if chk: return True
    else: return False

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b < 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for i in range(m) ]
        # print(n,m,xys)
        for i in range(m):
            if len(set(p)) == 1: print(1); break
            for j in range(i+1,m):
                if p[i] == p[j]:
                    continue
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        else: print(len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import product

def chk_in_rect(xy1,xy2):
    chk2in1 = True
    for i in range(4):
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk2in1 = False; break
    chk1in2 = True
    for i in range(4):
        for j in range(4):
            a = (xy2[(2*i+2)&7]-xy2[(2*i  )&7]) * (xy1[(2*j+1)&7]-xy2[(2*i+1)&7])
            b = (xy2[(2*i+3)&7]-xy2[(2*i+1)&7]) * (xy1[(2*j  )&7]-xy2[(2*i  )&7])
            if a > b: chk2in1 = False; break
    if chk2in1|chk1in2: return True
    else: return False

def chk_intersect(xy1,xy2):
    for i,j in product(range(4),repeat=2):
        a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
        a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
        b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
        b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
        if a*b <= 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for i in range(m) ]
        print(1)
        continue
        # print(n,m,xys)
        for i in range(m):
            if len(set(p)) == 1: print(1); break
            for j in range(i+1,m):
                if p[i] == p[j]:
                    continue
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        else: print(p,len(set(p)))

Submission status: Runtime Error

Solution code:
from sys import stdin

def chk_in_rect(xy1,xy2):
    chk2in1 = True
    for i in range(4):
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk2in1 = False; break
    chk1in2 = True
    for i in range(4):
        for j in range(4):
            a = (xy2[(2*i+2)&7]-xy2[(2*i  )&7]) * (xy1[(2*j+1)&7]-xy2[(2*i+1)&7])
            b = (xy2[(2*i+3)&7]-xy2[(2*i+1)&7]) * (xy1[(2*j  )&7]-xy2[(2*i  )&7])
            if a > b: chk2in1 = False; break
    if chk2in1|chk1in2: return True
    else: return False

def chk_intersect(xy1,xy2):
    for i in range(4):
        for j in range(4):
            a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
            a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
            b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
            b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
            if a*b <= 0 : return True
    else:
        return False

while(True):
    try:
        n = int(stdin.readline())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(stdin.readline())
        p = list(range(m))
        xys = [ list(map(int, stdin.readline().split())) for i in range(m) ]
        print(1)
        continue
        # print(n,m,xys)
        for i in range(m):
            if len(set(p)) == 1: print(1); break
            for j in range(i+1,m):
                if p[i] == p[j]:
                    continue
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        else: print(p,len(set(p)))

Submission status: Runtime Error

Solution code:

def chk_in_rect(xy1,xy2):
    chk2in1 = True
    for i in range(4):
        for j in range(4):
            a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
            b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
            if a > b: chk2in1 = False; break
    chk1in2 = True
    for i in range(4):
        for j in range(4):
            a = (xy2[(2*i+2)&7]-xy2[(2*i  )&7]) * (xy1[(2*j+1)&7]-xy2[(2*i+1)&7])
            b = (xy2[(2*i+3)&7]-xy2[(2*i+1)&7]) * (xy1[(2*j  )&7]-xy2[(2*i  )&7])
            if a > b: chk2in1 = False; break
    if chk2in1|chk1in2: return True
    else: return False

def chk_intersect(xy1,xy2):
    for i in range(4):
        for j in range(4):
            a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
            a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
            b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
            b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
            if a*b <= 0 : return True
    else:
        return False

while(True):
    try:
        n = int(input())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(input())
        p = list(range(m))
        xys = [ list(map(int, input().split())) for i in range(m) ]
        print(1)
        continue
        # print(n,m,xys)
        for i in range(m):
            if len(set(p)) == 1: print(1); break
            for j in range(i+1,m):
                if p[i] == p[j]:
                    continue
                if chk_in_rect(xys[i],xys[j]):
                    # print("in_rect")
                    p = [i if e==j else e for e in p]
                    continue
                if chk_intersect(xys[i],xys[j]):
                    # print("intersect")
                    p = [i if e==j else e for e in p]
                    continue
        else: print(p,len(set(p)))

Submission status: Runtime Error

Solution code:

# def chk_in_rect(xy1,xy2):
#     chk2in1 = True
#     for i in range(4):
#         for j in range(4):
#             a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
#             b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
#             if a > b: chk2in1 = False; break
#     chk1in2 = True
#     for i in range(4):
#         for j in range(4):
#             a = (xy2[(2*i+2)&7]-xy2[(2*i  )&7]) * (xy1[(2*j+1)&7]-xy2[(2*i+1)&7])
#             b = (xy2[(2*i+3)&7]-xy2[(2*i+1)&7]) * (xy1[(2*j  )&7]-xy2[(2*i  )&7])
#             if a > b: chk2in1 = False; break
#     if chk2in1|chk1in2: return True
#     else: return False

# def chk_intersect(xy1,xy2):
#     for i in range(4):
#         for j in range(4):
#             a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
#             a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
#             b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
#             b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
#             if a*b <= 0 : return True
#     else:
#         return False

while(True):
    try:
        n = int(input())
        if not n: break
    except:
        break
    for _ in range(n):
        m = int(input())
        p = list(range(m))
        xys = [ list(map(int, input().split())) for i in range(m) ]
        print(1)
        continue
        # # print(n,m,xys)
        # for i in range(m):
        #     if len(set(p)) == 1: print(1); break
        #     for j in range(i+1,m):
        #         if p[i] == p[j]:
        #             continue
        #         if chk_in_rect(xys[i],xys[j]):
        #             # print("in_rect")
        #             p = [i if e==j else e for e in p]
        #             continue
        #         if chk_intersect(xys[i],xys[j]):
        #             # print("intersect")
        #             p = [i if e==j else e for e in p]
        #             continue
        # else: print(p,len(set(p)))

Submission status: Runtime Error

Solution code:

# def chk_in_rect(xy1,xy2):
#     chk2in1 = True
#     for i in range(4):
#         for j in range(4):
#             a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
#             b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
#             if a > b: chk2in1 = False; break
#     chk1in2 = True
#     for i in range(4):
#         for j in range(4):
#             a = (xy2[(2*i+2)&7]-xy2[(2*i  )&7]) * (xy1[(2*j+1)&7]-xy2[(2*i+1)&7])
#             b = (xy2[(2*i+3)&7]-xy2[(2*i+1)&7]) * (xy1[(2*j  )&7]-xy2[(2*i  )&7])
#             if a > b: chk2in1 = False; break
#     if chk2in1|chk1in2: return True
#     else: return False

# def chk_intersect(xy1,xy2):
#     for i in range(4):
#         for j in range(4):
#             a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
#             a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
#             b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
#             b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
#             if a*b <= 0 : return True
#     else:
#         return False

while(True):
    n = int(input())
    if not n: break
    for _ in range(n):
        m = int(input())
        p = list(range(m))
        xys = [ list(map(int, input().split())) for i in range(m) ]
        print(1)
        continue
        # # print(n,m,xys)
        # for i in range(m):
        #     if len(set(p)) == 1: print(1); break
        #     for j in range(i+1,m):
        #         if p[i] == p[j]:
        #             continue
        #         if chk_in_rect(xys[i],xys[j]):
        #             # print("in_rect")
        #             p = [i if e==j else e for e in p]
        #             continue
        #         if chk_intersect(xys[i],xys[j]):
        #             # print("intersect")
        #             p = [i if e==j else e for e in p]
        #             continue
        # else: print(p,len(set(p)))

Submission status: Runtime Error

Solution code:

# def chk_in_rect(xy1,xy2):
#     chk2in1 = True
#     for i in range(4):
#         for j in range(4):
#             a = (xy1[(2*i+2)&7]-xy1[(2*i  )&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+1)&7])
#             b = (xy1[(2*i+3)&7]-xy1[(2*i+1)&7]) * (xy2[(2*j  )&7]-xy1[(2*i  )&7])
#             if a > b: chk2in1 = False; break
#     chk1in2 = True
#     for i in range(4):
#         for j in range(4):
#             a = (xy2[(2*i+2)&7]-xy2[(2*i  )&7]) * (xy1[(2*j+1)&7]-xy2[(2*i+1)&7])
#             b = (xy2[(2*i+3)&7]-xy2[(2*i+1)&7]) * (xy1[(2*j  )&7]-xy2[(2*i  )&7])
#             if a > b: chk2in1 = False; break
#     if chk2in1|chk1in2: return True
#     else: return False

# def chk_intersect(xy1,xy2):
#     for i in range(4):
#         for j in range(4):
#             a = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+1)&7]-xy1[(2*i+3)&7])
#             a+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j  )&7])
#             b = (xy1[(2*i  )&7]-xy1[(2*i+2)&7]) * (xy2[(2*j+3)&7]-xy1[(2*i+3)&7])
#             b+= (xy1[(2*i+1)&7]-xy1[(2*i+3)&7]) * (xy2[(2*i  )&7]-xy1[(2*j+2)&7])
#             if a*b <= 0 : return True
#     else:
#         return False

while(True):
    n = int(input())
    if not n: break
    for _ in range(n):
        m = int(input())
        # p = list(range(m))
        xys = [ list(map(int, input().split())) for i in range(m) ]
        print(1)
        continue
        # # print(n,m,xys)
        # for i in range(m):
        #     if len(set(p)) == 1: print(1); break
        #     for j in range(i+1,m):
        #         if p[i] == p[j]:
        #             continue
        #         if chk_in_rect(xys[i],xys[j]):
        #             # print("in_rect")
        #             p = [i if e==j else e for e in p]
        #             continue
        #         if chk_intersect(xys[i],xys[j]):
        #             # print("intersect")
        #             p = [i if e==j else e for e in p]
        #             continue
        # else: print(p,len(set(p)))

Submission status: Runtime Error

Solution code:
while(True):
    n = int(input())
    if not n: break
    for _ in range(n):
        m = int(input())
        # p = list(range(m))
        xys = [ list(map(int, input().split())) for i in range(m) ]
        print(1)
        continue

Submission status: Runtime Error

Solution code:
while(True):
    n = int(input())
    if not n: break
    for _ in range(n):
        m = int(input())
        # p = list(range(m))
        xys = [ map(int, input().split()) for i in range(m) ]
        print(1)
        continue

Submission status: Runtime Error

Solution code:
while(True):
    n = int(input())
    if not n: break
    for _ in range(n):
        m = int(input())
        # p = list(range(m))
        xys = [ input() for i in range(m) ]
        print(1)
        continue