QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543210#8677. Carl’s VacationqwerasdfWA 17ms11140kbPython32.5kb2024-09-01 15:04:142024-09-01 15:04:15

Judging History

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

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

answer

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

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 and dot(n0, sub(d, a)) >= 0) and (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 = (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)
        

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 11028kb

input:

1 0 0 0 10000
99999 10000 10000 10000 10000

output:

76118.700049220477057967010551545603294009129965315734628098609977795817607001141238554638162978880124178883541254744495001304964821133021089326928468321182035342826433750183042354170799995364402962011

result:

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

Test #2:

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

input:

10000 10000 10000 0 10000
0 0 0 10000 10000

output:

32360.679774997896964091736687312762354406183596115257242708972454105209256378048994144144083787822749695081761507737835042532677244470738635863601215334527088667781731918791658112766453226398565805358

result:

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

Test #3:

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

input:

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

output:

107.36555507899020063181519267199596934757053908363671698937980475853531860407214260464361080355847565164250998661474397383632420822441228162300866925060766079571188720466684641153960220179094859118445

result:

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

Test #4:

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

input:

0 0 100 100 20
23 23 18 18 2

output:

88.056757050574897791675814304416573305568653315275069041834879881907076751099711488758029262298249299306794984515062873808553215038163630029726683713978822163731348701893205169509785093591355211377250

result:

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

Test #5:

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

input:

0 0 100 100 20
100 100 105 95 2

output:

107.36555507899020063181519267199596934757053908363671698937980475853531860407214260464361080355847565164250998661474397383632420822441228162300866925060766079571188720466684641153960220179094859118445

result:

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

Test #6:

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

input:

0 0 100 100 20
44 156 49 151 2

output:

77.704520217706588532073354306333983251622074308501572376462875174719571795260660456289966757287974921510079996787946985550991550583251243854221840298971166057017247301281960711525773307830178034513549

result:

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

Test #7:

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

input:

0 0 100 100 20
200 0 205 5 2

output:

224.52803515684048884992525192242861316688245313050388469340929080678915924788042474345568181507423008411527715228863927045930676633381423301750927574734208006626807578248335861430782823977689420869961

result:

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

Test #8:

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

input:

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

output:

84.368195798321845901307466927138941230469881041545667695829970791757416251983848724182845522898995140928106910573773223484143507089193179139268945031092545341275654572415056301733412072721641054471576

result:

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

Test #9:

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

input:

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

output:

107.36555507899020063181519267199596934757053908363671698937980475853531860407214260464361080355847565164250998661474397383632420822441228162300866925060766079571188720466684641153960220179094859118445

result:

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

Test #10:

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

input:

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

output:

83.294612444407063060351671934514420070474595184974824061357028241053151568573834562482390874712451109978873543325809458723874924970907596769170680207201103132583705329755172850274275318821225856056697

result:

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

Test #11:

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

input:

0 0 30 0 20
50 20 80 20 20

output:

72.801098892805182710973024915270327937776696825764774383781817912841157386249051833295794090809267521926345704730578121591478607551197854097861346782052065719981334333481202942475392280650066566606151

result:

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

Test #12:

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

input:

0 0 30 0 20
50 20 80 20 140

output:

186.87494827575004276129285197696202562593532057916639470460119490740045106120181909105756267942249200778367349518345932549570515471556866390299522991877769877212094846405241279153356770106511693536553

result:

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

Test #13:

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

input:

0 0 30 0 140
50 20 80 20 140

output:

302.26495376120430859833579933799789867849361818520256091908379999184449991926005659606677552114572733024454021355827220115694848437843307044849497095912708721146773725699165616556145509346330918060852

result:

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

Test #14:

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

input:

0 0 30 0 500
50 20 80 20 140

output:

661.32879300502544006004900802907615675215495682378507756421128575585686273854634697237516317487346961255929328289432819946600552528176054938657010073635771701480139624134149498647977119430936158369965

result:

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

Test #15:

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

input:

0 0 30 0 500
50 20 80 20 500

output:

1020.6458719613877297333897855815683658153426741692233433036093999168376651909259928979768806028013888532257901726344029155867046601729156848934875866614006988286102257131265055348724028499511308269122

result:

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

Test #16:

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

input:

0 0 30 0 500
50 20 80 20 2000

output:

2520.3614737461241393463005611836964459759672377326322808832752693663798303205025039499481411255562406859425177995113913302948366881560736820725820096107899784130278840573073247884124043646501073147282

result:

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

Test #17:

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

input:

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

output:

16631.267204637919938278416880202082052861470453109024956495576244197761210707971443617540794044772953869539287111231825872375927877602863139974480525684438810095705197530082174049608082690026274624068

result:

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

Test #18:

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

input:

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

output:

14848.097967205740800899643289202404303283702653410510648666868486407540894989931278381842123474802978842777735899883161331767379324733231853091541421225244665599350915509010142262974475802419767845231

result:

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

Test #19:

score: -100
Wrong Answer
time: 16ms
memory: 10988kb

input:

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

output:

1000000000

result:

wrong answer 1st numbers differ - expected: '18844.4706205', found: '1000000000.0000000', error = '53064.9640241'