QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543156#8677. Carl’s VacationqwerasdfWA 15ms10900kbPython32.4kb2024-09-01 14:32:032024-09-01 14:32:04

Judging History

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

  • [2024-09-01 14:32:04]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:10900kb
  • [2024-09-01 14:32:03]
  • 提交

answer

import math

def rot90(a): # 반시계
    return (-a[1], a[0])

def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]

def cross(a, b):
    return a[0] * b[1] - a[1] * b[0]

def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def sub(a, b):
    return (a[0] - b[0], a[1] - b[1])

def mul(a, b): # a: 스칼라
    return (a * b[0], a * b[1])

def dist(a, b):
    t = sub(b, a)
    return math.sqrt(dot(t, t))
    

def is_facing(a, b, c, d):
    n0 = rot90(sub(a, b))
    n1 = rot90(sub(c, d))
    return dot(n0, sub(c, a)) >= 0 and dot(n0, sub(d, a)) >= 0 or dot(n1, sub(a, c)) >= 0 and dot(n1, sub(b, c)) >= 0

def make_tri(a, b, h):
    norm = rot90(sub(b, a))
    sq = dot(norm, norm)
    k = math.sqrt((math.sqrt(sq) / 2) ** 2 + h ** 2)
    c = add(mul(k / math.sqrt(sq), norm), mul(0.5, add(a, b)))
    return (a, b, c)

def is_in(p, a, b, x):
    v0 = sub(a, p)
    v1 = sub(x, p)
    v2 = sub(b, p)
    
    return cross(v0, v1) >= 0 and cross(v1, v2) >= 0

ls = []
for i in range(2):
    ls.append([*map(int, input().split())])
pyra = []
tmp = []
for l in ls:
    x = l[0]
    y = l[1]
    dx = l[2] - x
    dy = l[3] - y
    tmp = [(x, y), (x + dx, y + dy), (x + dx - dy, y + dy + dx), (x - dy, y + dx), l[4]]
    pyra.append(tmp)

mn = 1e9

for i in range(4):
    for j in range(4):
        a = pyra[0][i % 4]
        b = pyra[0][(i + 1) % 4]
        c = pyra[1][j % 4]
        d = pyra[1][(j + 1) % 4]
        if is_facing(a, b, c, d):
            t0 = make_tri(a, b, pyra[0][4])
            t1 = make_tri(c, d, pyra[1][4])
            #print(t0, t1)

            a, b, c = t0
            d, e, f = t1

            # case work
            if is_in(c, a, b, f) and is_in(f, d, e, c):
                mn = min(mn, dist(c, f))
                #print('cf')

            if is_in(c, a, b, d):
                mn = min(mn, dist(c, d) + dist(d, f))
                #print('cdf')

            if is_in(c, a, b, e):
                mn = min(mn, dist(c, e) + dist(e, f))
                #print('cef')

            if is_in(f, d, e, a):
                mn = min(mn, dist(c, a) + dist(a, f))
                #print('caf')

            if is_in(f, d, e, b):
                mn = min(mn, dist(c, b) + dist(b, f))
                #print('cbf')

            mn = min(mn, dist(c, a) + dist(f, d) + min([dist(a, d), dist(a, e), dist(b, d), dist(b, e)]))

print(mn)
        

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 10776kb

input:

1 0 0 0 10000
99999 10000 10000 10000 10000

output:

76118.70004922048

result:

ok found '76118.7000492', expected '76118.7000492', error '0.0000000'

Test #2:

score: 0
Accepted
time: 11ms
memory: 10720kb

input:

10000 10000 10000 0 10000
0 0 0 10000 10000

output:

32360.6797749979

result:

ok found '32360.6797750', expected '32360.6797750', error '0.0000000'

Test #3:

score: 0
Accepted
time: 12ms
memory: 10720kb

input:

0 0 100 100 20
0 0 -5 -5 2

output:

107.36555507899021

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #4:

score: 0
Accepted
time: 5ms
memory: 10872kb

input:

0 0 100 100 20
23 23 18 18 2

output:

88.0567570505749

result:

ok found '88.0567571', expected '88.0567571', error '0.0000000'

Test #5:

score: 0
Accepted
time: 9ms
memory: 10792kb

input:

0 0 100 100 20
100 100 105 95 2

output:

107.36555507899023

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #6:

score: 0
Accepted
time: 7ms
memory: 10836kb

input:

0 0 100 100 20
44 156 49 151 2

output:

77.7045202177066

result:

ok found '77.7045202', expected '77.7045202', error '0.0000000'

Test #7:

score: 0
Accepted
time: 15ms
memory: 10840kb

input:

0 0 100 100 20
200 0 205 5 2

output:

224.5280351568405

result:

ok found '224.5280352', expected '224.5280352', error '0.0000000'

Test #8:

score: 0
Accepted
time: 10ms
memory: 10768kb

input:

0 0 100 100 20
-29 171 -24 176 2

output:

84.36819579832185

result:

ok found '84.3681958', expected '84.3681958', error '0.0000000'

Test #9:

score: 0
Accepted
time: 5ms
memory: 10756kb

input:

0 0 100 100 20
-100 100 -105 105 2

output:

107.36555507899023

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #10:

score: 0
Accepted
time: 8ms
memory: 10900kb

input:

0 0 100 100 20
-69 69 -74 74 2

output:

83.29461244440708

result:

ok found '83.2946124', expected '83.2946124', error '0.0000000'

Test #11:

score: 0
Accepted
time: 3ms
memory: 10836kb

input:

0 0 30 0 20
50 20 80 20 20

output:

72.80109889280519

result:

ok found '72.8010989', expected '72.8010989', error '0.0000000'

Test #12:

score: -100
Wrong Answer
time: 15ms
memory: 10724kb

input:

0 0 30 0 20
50 20 80 20 140

output:

120.0935969402469

result:

wrong answer 1st numbers differ - expected: '186.8749483', found: '120.0935969', error = '0.3573585'