QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863738 | #3001. Piece of Cake | isWFnoya# | RE | 14ms | 14592kb | Python3 | 2.2kb | 2025-01-19 21:49:45 | 2025-01-19 21:49:54 |
Judging History
answer
import math
eps = 1e-9
pi = math.acos(-1.0)
inf = 40000
def sgn(x):
if x < -eps:
return -1
elif x > eps:
return 1
else:
return 0
def cmp(x, y):
return sgn(x - y)
def C(n, m):
if n <= m:
return 1.0
return fac[n] / fac[m] / fac[n - m]
# 定义一个类来表示二维点
class Point:
def __init__(self, x=0.0, y=0.0):
self.x = x
self.y = y
def input(self):
x2, y2 = map(float, input().split())
self.x = x2
self.y = y2
def __add__(self, s):
return Point(self.x + s.x, self.y + s.y)
def __sub__(self, s):
return Point(self.x - s.x, self.y - s.y)
def __mul__(self, k):
return Point(self.x * k, self.y * k)
def __truediv__(self, k):
return Point(self.x / k, self.y / k)
def dot(self, a):
return self.x * a.x + self.y * a.y
def cross(self, a):
return self.x * a.y - self.y * a.x
def cross(s, t):
return s.x * t.y - s.y * t.x
# 计算组合数 C(n, m)
fac = [1] * 3000
for i in range(1, 3000):
fac[i] = fac[i - 1] * i
def solve():
# 预先计算所有的阶乘
fac[0] = 1
for i in range(1, 3000):
fac[i] = fac[i - 1] * i
# 计算组合数 C(1000, 900)
# print(f"{C(1000, 900):.8f}")
# return
# 读取 n 和 k
n, k = map(int, input().split())
# n = 3000
# k = 10
p = []
# 输入所有的点
for i in range(n):
point = Point()
point.input()
p.append(point)
p.reverse() # 反转点列表
ans = 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.0 / fac[k - 2] / C(n, k)
print(f"{result:.8f}")
if __name__ == "__main__":
T = 1
# T = int(input()) # 可选输入多个测试案例
while T > 0:
solve()
T -= 1
詳細信息
Test #1:
score: 100
Accepted
time: 14ms
memory: 14592kb
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
Runtime Error
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...