QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#543296#8677. Carl’s VacationqwerasdfWA 17ms11136kbPython32.5kb2024-09-01 15:43:302024-09-01 15:43:32

Judging History

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

  • [2024-09-01 15:43:32]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:11136kb
  • [2024-09-01 15:43:30]
  • 提交

answer

import math
from decimal import *
getcontext().prec = 30

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 dot(t, t).sqrt()
    

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

def make_tri(a, b, h):
    norm = rot90(sub(b, a))
    sq = dot(norm, norm)
    k = (sq / 4 + h ** 2).sqrt()
    c = add(mul(k / sq.sqrt(), norm), mul(Decimal(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(Decimal, 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 = Decimal(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)
        

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 11024kb

input:

1 0 0 0 10000
99999 10000 10000 10000 10000

output:

76118.7000492204770579670105516

result:

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

Test #2:

score: 0
Accepted
time: 16ms
memory: 10920kb

input:

10000 10000 10000 0 10000
0 0 0 10000 10000

output:

32360.6797749978969640917366874

result:

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

Test #3:

score: 0
Accepted
time: 13ms
memory: 11108kb

input:

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

output:

107.365555078990200631815192672

result:

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

Test #4:

score: 0
Accepted
time: 17ms
memory: 10920kb

input:

0 0 100 100 20
23 23 18 18 2

output:

88.0567570505748977916758143042

result:

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

Test #5:

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

input:

0 0 100 100 20
100 100 105 95 2

output:

107.365555078990200631815192671

result:

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

Test #6:

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

input:

0 0 100 100 20
44 156 49 151 2

output:

77.7045202177065885320733543063

result:

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

Test #7:

score: 0
Accepted
time: 13ms
memory: 11020kb

input:

0 0 100 100 20
200 0 205 5 2

output:

224.528035156840488849925251922

result:

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

Test #8:

score: 0
Accepted
time: 16ms
memory: 11008kb

input:

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

output:

84.3681957983218459013074669270

result:

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

Test #9:

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

input:

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

output:

107.365555078990200631815192671

result:

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

Test #10:

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

input:

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

output:

83.2946124444070630603516719345

result:

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

Test #11:

score: 0
Accepted
time: 17ms
memory: 11076kb

input:

0 0 30 0 20
50 20 80 20 20

output:

72.8010988928051827109730249153

result:

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

Test #12:

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

input:

0 0 30 0 20
50 20 80 20 140

output:

186.874948275750042761292851977

result:

ok found '186.8749483', expected '186.8749483', error '0.0000000'

Test #13:

score: 0
Accepted
time: 17ms
memory: 10968kb

input:

0 0 30 0 140
50 20 80 20 140

output:

302.264953761204308598335799337

result:

ok found '302.2649538', expected '302.2649538', error '0.0000000'

Test #14:

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

input:

0 0 30 0 500
50 20 80 20 140

output:

661.328793005025440060049008028

result:

ok found '661.3287930', expected '661.3287930', error '0.0000000'

Test #15:

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

input:

0 0 30 0 500
50 20 80 20 500

output:

1020.64587196138772973338978558

result:

ok found '1020.6458720', expected '1020.6458720', error '0.0000000'

Test #16:

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

input:

0 0 30 0 500
50 20 80 20 2000

output:

2520.36147374612413934630056118

result:

ok found '2520.3614737', expected '2520.3614737', error '0.0000000'

Test #17:

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

input:

1137 -1096 229 -599 6253
5792 -405 3433 -9660 2912

output:

16631.2672046379199382784168802

result:

ok found '16631.2672046', expected '16631.2672046', error '0.0000000'

Test #18:

score: 0
Accepted
time: 17ms
memory: 11076kb

input:

-1458 4365 -759 -5184 408
8891 -5111 2941 -8564 6966

output:

14848.0979672057408008996432892

result:

ok found '14848.0979672', expected '14848.0979672', error '0.0000000'

Test #19:

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

input:

2289 1693 -2539 850 7414
-4989 3660 8091 2109 6915

output:

18844.4706205017155162303776915

result:

ok found '18844.4706205', expected '18844.4706205', error '0.0000000'

Test #20:

score: 0
Accepted
time: 13ms
memory: 11032kb

input:

5431 8457 6717 -6624 2204
-5504 -5607 4032 -674 7792

output:

20847.8621668110330627289355954

result:

ok found '20847.8621668', expected '20847.8621668', error '0.0000000'

Test #21:

score: 0
Accepted
time: 16ms
memory: 11076kb

input:

4274 -9998 -3313 -2647 4590
-792 1334 5701 -8048 3257

output:

16956.4834717883378781648076546

result:

ok found '16956.4834718', expected '16956.4834718', error '0.0000000'

Test #22:

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

input:

-1563 -4648 1926 -2970 5843
-1600 9113 -1007 5823 7516

output:

19666.6200192503750008105723938

result:

ok found '19666.6200193', expected '19666.6200193', error '0.0000000'

Test #23:

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

input:

-6957 -1204 -2026 2849 1571
9178 1160 -3263 -6525 9297

output:

22798.2691656399858391318615991

result:

ok found '22798.2691656', expected '22798.2691656', error '0.0000000'

Test #24:

score: 0
Accepted
time: 17ms
memory: 11096kb

input:

-5254 4877 5836 -1945 4282
8106 -8783 7076 -2291 6168

output:

17820.1271048618932973341083871

result:

ok found '17820.1271049', expected '17820.1271049', error '0.0000000'

Test #25:

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

input:

2278 -7979 -200 -9432 528
-8604 1343 -5214 2428 8005

output:

22690.4150723922763021818689252

result:

ok found '22690.4150724', expected '22690.4150724', error '0.0000000'

Test #26:

score: 0
Accepted
time: 16ms
memory: 11012kb

input:

5003 277 737 -3626 2886
3492 4353 -446 5788 2426

output:

10058.3916191793300385234148946

result:

ok found '10058.3916192', expected '10058.3916192', error '0.0000000'

Test #27:

score: 0
Accepted
time: 13ms
memory: 11028kb

input:

-6582 -2629 -1742 6935 5531
-2010 1455 1794 -3461 9066

output:

20018.3757266857331131529775798

result:

ok found '20018.3757267', expected '20018.3757267', error '0.0000000'

Test #28:

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

input:

-8174 -1075 -6736 -2685 6615
-2151 4184 -1716 -308 5064

output:

16260.3532322229916596585729491

result:

ok found '16260.3532322', expected '16260.3532322', error '0.0000000'

Test #29:

score: 0
Accepted
time: 16ms
memory: 11076kb

input:

5291 1243 8982 5204 8450
-1177 -5306 -1390 2460 8858

output:

23316.8500582543528176813940458

result:

ok found '23316.8500583', expected '23316.8500583', error '0.0000000'

Test #30:

score: 0
Accepted
time: 13ms
memory: 11008kb

input:

-4229 2060 9017 -2659 5812
9887 -9973 5460 -2671 4205

output:

18310.3049215939742296615277916

result:

ok found '18310.3049216', expected '18310.3049216', error '0.0000000'

Test #31:

score: 0
Accepted
time: 13ms
memory: 11072kb

input:

0 0 8 0 3
0 8 8 8 3

output:

10.000

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #32:

score: 0
Accepted
time: 13ms
memory: 10976kb

input:

0 0 8 0 2
8 8 16 8 2

output:

12.0000000000000000000000000000

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #33:

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

input:

0 0 8 0 2
10 10 18 10 2

output:

14.8284271247461900976033774484

result:

ok found '14.8284271', expected '14.8284271', error '0.0000000'

Test #34:

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

input:

0 0 8 0 100000
10 10 18 10 100000

output:

200002.828747124745934097603787

result:

ok found '200002.8287471', expected '200002.8287471', error '0.0000000'

Test #35:

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

input:

51412 80788 39091 71527 97605
6327 44899 20415 -12571 86627

output:

194757.486833428939427897955768

result:

ok found '194757.4868334', expected '194757.4868334', error '0.0000000'

Test #36:

score: 0
Accepted
time: 13ms
memory: 11108kb

input:

-43347 56743 17244 83573 86143
-90081 -3018 -22063 -95528 26489

output:

179973.341845177795468225820912

result:

ok found '179973.3418452', expected '179973.3418452', error '0.0000000'

Test #37:

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

input:

88637 -28248 308 -92620 47395
-57673 62668 -66785 923 49207

output:

210116.821817332454474103327589

result:

ok found '210116.8218173', expected '210116.8218173', error '0.0000000'

Test #38:

score: 0
Accepted
time: 16ms
memory: 11004kb

input:

59768 12643 57116 -71451 64957
-43638 42191 -37837 9851 1875

output:

171578.651505342092695804688499

result:

ok found '171578.6515053', expected '171578.6515053', error '0.0000000'

Test #39:

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

input:

-46206 -30845 -28470 3652 33497
74620 -92045 75046 -19320 48537

output:

147174.131714614665692990122404

result:

ok found '147174.1317146', expected '147174.1317146', error '0.0000000'

Test #40:

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

input:

65899 65734 27624 70256 81635
-97389 -56422 -91684 -53179 88643

output:

317109.421796759350128053022335

result:

ok found '317109.4217968', expected '317109.4217968', error '0.0000000'

Test #41:

score: 0
Accepted
time: 16ms
memory: 11024kb

input:

-25117 -50391 569 -34721 73972
-90107 -83510 -46359 -95477 83257

output:

174084.670254181905471622985368

result:

ok found '174084.6702542', expected '174084.6702542', error '0.0000000'

Test #42:

score: -100
Wrong Answer
time: 17ms
memory: 10960kb

input:

6832 -56636 7968 -59867 82961
6289 -49692 -56413 -38910 90946

output:

174287.458482587657492010054901

result:

wrong answer 1st numbers differ - expected: '184208.6118875', found: '174287.4584826', error = '0.0538582'