QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708816 | #5679. Linked Triangles | mgoldy925# | WA | 15ms | 10564kb | Python3 | 2.9kb | 2024-11-04 07:40:04 | 2024-11-04 07:40:05 |
Judging History
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()
详细
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'