QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#863745#3001. Piece of CakeisWFnoya#TL 15ms10496kbPython31.8kb2025-01-19 21:54:212025-01-19 21:54:31

Judging History

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

  • [2025-01-19 21:54:31]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:10496kb
  • [2025-01-19 21:54:21]
  • 提交

answer

import math
from decimal import Decimal, getcontext

# 设置 Decimal 模块的全局精度为 50 位(可以根据需要调整)
getcontext().prec = 50

def C(n, m):
    if n <= m:
        return Decimal(1.0)
    return fac[n] / fac[m] / fac[n - m]

# 定义一个类来表示二维点
class Point:
    def __init__(self, x=0.0, y=0.0):
        self.x = Decimal(x)
        self.y = Decimal(y)

    def input(self):
        x2, y2 = map(Decimal, input().split())
        self.x = x2
        self.y = y2

def cross(s, t):
    return s.x * t.y - s.y * t.x

# 计算组合数 C(n, m)
fac = [Decimal(1)] * 3000
for i in range(1, 3000):
    fac[i] = fac[i - 1] * i

def solve():
    # 预先计算所有的阶乘
    fac[0] = Decimal(1)
    for i in range(1, 3000):
        fac[i] = fac[i - 1] * i

    # 计算组合数 C(2999, 900)
    # print(f"{C(2999, 900):.8f}")
    # return

    # 读取 n 和 k
    n, k = map(int, input().split())
    p = []

    # 输入所有的点
    for i in range(n):
        point = Point()
        point.input()
        p.append(point)

    p.reverse()  # 反转点列表

    ans = Decimal(0.0)
    for i in range(n):
        for j in range(i + 1, n):
            c = cross(p[i], p[j])
            cnt = n - (j - i + 1)
            if cnt >= k - 2:
                ans += c * fac[cnt] / fac[cnt - (k - 2)]
            
            cnt = j - i - 1
            if cnt >= k - 2:
                ans -= c * fac[cnt] / fac[cnt - (k - 2)]

    # 输出最终结果,使用 8 位小数
    result = ans / 2 / fac[k - 2] / C(n, k)
    print(f"{result:.8f}")

if __name__ == "__main__":
    T = 1
    # T = int(input())  # 可选输入多个测试案例
    while T > 0:
        solve()
        T -= 1

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 10496kb

input:

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

output:

1.92794640

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: