QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708816#5679. Linked Trianglesmgoldy925#WA 15ms10564kbPython32.9kb2024-11-04 07:40:042024-11-04 07:40:05

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 07:40:05]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:10564kb
  • [2024-11-04 07:40:04]
  • 提交

answer

import sys
import math
from itertools import combinations

input = sys.stdin.readline

ints = lambda : map(int, input().split())
floats = lambda : map(float, input().split())
intsl = lambda : list(ints())
floatsl = lambda : list(floats())


def cross(v1, v2):
    (a, b, c), (x, y, z) = v1, v2
    return [b*z - c*y, c*x - z*a, a*y - b*x]

def dot(v1, v2):
    return sum(ai*bi for ai, bi in zip(v1, v2))

def sub(v1, v2):
    return [ai-bi for ai, bi in zip(v1, v2)]

def add(v1, v2):
    return [ai+bi for ai, bi in zip(v1, v2)]

def mult(v, c):
    return [c*vi for vi in v]

def norm(v):
    return sum(vi*vi for vi in v)

def det(mat):
    # ASSUMING MAT IS LIST OF COLUMN VECTORS
    # actually that doesn't matter, det(A) = det(A^T)
    (a,b,c), (s,r,t), (x,y,z) = mat
    return a*(r*z - y*t) - b*(s*z - x*t) + c*(s*y - x*r)

def pt_plane_inter(n, x, y, pt):
    t = dot(n, sub(pt, y)) / dot(n, sub(x, y))
    return add(mult(sub(x, y), t), y)

def pt_lin_dist(pt, line, bp):
    u = mult(line, 1/norm(line))
    w = sub(pt, bp)
    return norm(sub(w, mult(u, dot(w, u))))

def pt_in_tri(pt, a, b, c):
    trips = [(a,b,c), (b,c,a), (c,a,b)]
    for x, y, z in trips:
        dist = pt_lin_dist(pt, sub(x, y), x)
        dist_max = pt_lin_dist(z, sub(x, y), x)
        if dist >= dist_max:
            return False
    return True


def main():
    ptsss = [floatsl() for _ in range(6)]
    links = []

    i = 0
    for j, k in combinations(range(1, 6), 2):
        A, B, C = ptsss[i], ptsss[j], ptsss[k]
        ii, jj, kk = [l for l in range(6) if l not in [i, j, k]]
        D, E, F = ptsss[ii], ptsss[jj], ptsss[kk]

        if cross(sub(A,B), sub(A,C)) == 0 or cross(sub(D,E), sub(D,F)) == 0:
            continue

        n = cross(sub(A, B), sub(A, C))
        dets = [(det([sub(A, B), sub(A, C), sub(A, pt)]), pt) for pt in [D, E, F]]
        dets.sort()
        vals = [d for d, _ in dets]
        pts = [pt for _, pt in dets]

        if 0 in vals:
            if vals.count(0) > 1:
                continue
            
            pt1, pt2, pt3 = pts
            p = pt_plane_inter(n, pt1, pt3, A)

            if not pt_in_tri(p, A, B, C):
                links.append(sorted((j, k)))

        else:
            if vals[0] > 0 or vals[-1] < 0:
                continue

            pt1, pt2, pt3 = pts
            if sum(deti < 0 for deti in vals) > 1:
                pt1, pt2, pt3 = pt3, pt1, pt2
            
            p1 = pt_plane_inter(n, pt1, pt2, A)
            p2 = pt_plane_inter(n, pt1, pt3, A)

            bools = [pt_in_tri(p1, A, B, C), pt_in_tri(p2, A, B, C)]
            if True in bools and False in bools:
                links.append(sorted((j, k)))
            

    print(len(links))
    links.sort()
    for j, k in links:
        print(j+1, k+1)


if __name__ == "__main__":
    main()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 10564kb

input:

1 0 0
-1 0 0
0 1 0.2
0 -1 0.2
0.2 0.2 1
0.2 0.2 -1

output:

1
5 6

result:

wrong answer 1st lines differ - expected: '3', found: '1'