QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395150#3001. Piece of Cakeohiostatescarlet#TL 0ms9792kbPython3836b2024-04-21 08:27:002024-04-21 08:27:01

Judging History

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

  • [2024-04-21 08:27:01]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:9792kb
  • [2024-04-21 08:27:00]
  • 提交

answer


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

def area(arr):
    ans = cross(arr[-1], arr[0])
    for a, b in zip(arr, arr[1:]):
        ans += cross(a, b)
    return abs(ans) / 2


n, select = map(int, input().split())
k = n - select

comp = [1 for _ in range(k+1)]

if len(comp) > 1:
    comp[1] = k * (n - k - 1) * (n - k) / (n * (n - 1) * (n - 2))
    for y in range(2, len(comp)):
        comp[y] = comp[y-1] / (n - y - 1) * (k - y + 1)


p = [list(map(float, input().split())) for _ in range(n)]


total = area(p)
for start in range(n):
    a = 0
    points = [p[start], [0, 0], p[(start + 1) % n]]
    for y in range(1, k+1):
        end = start + y + 1
        points[1] = points[2]
        points[2] = p[end%n]
        a += area(points)
        total -= a * comp[y]
print(total)


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9792kb

input:

3 3
-5.236334 -8.519438
-9.987847 -0.492878
-9.994555 0.329962

output:

1.927946396220003

result:

ok found '1.9279464', expected '1.9279464', error '0.0000000'

Test #2:

score: -100
Time Limit Exceeded

input:

2496 3
-9.999961 0.028130
-9.999655 0.083151
-9.999641 0.084830
-9.999572 0.092537
-9.999474 0.102653
-9.999366 0.112678
-9.999329 0.115862
-9.998360 0.181104
-9.998033 0.198381
-9.997191 0.237035
-9.995264 0.307754
-9.993680 0.355494
-9.992454 0.388414
-9.992180 0.395407
-9.992030 0.399190
-9.99086...

output:


result: