@ThucNguyen1/

CHQUEENS

Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
T = int(input())

for _ in range(T):
  n, m, x, y = list(map(int, input().split()))
  # print('-----')
  # print(n, m, x, y)
  x -= 1
  y -= 1
  c = n*m -1
  total = c*(c-1) // 2
  count = 0
  # print('tong so cach dat:', total)
  hor = (n-1) * m*(m-1) // 2
  hor += y*(y-1)//2
  c = m-y-1
  hor += c*(c-1)//2
  # print('tong so cach hang ngang an nhau:', hor)
  ver = (m-1) * n*(n-1) // 2
  ver += x*(x-1)//2
  c = n-x-1
  ver += c*(c-1)//2
  # print('tong so cach hang doc an nhau:', ver)

  # so cach dat theo duong cheo
  # m>=n:
  # moi chieu(cheo chinh va phu:)
  # (m-n+1)*C(2,n) + 2(C(2,2) + C(2,3) + ... + C(2,n-1))
  dia = 0
  N = min(m, n)
  M = max(m, n)
  dia += (M-N+1) * N * (N-1) // 2
  for i in range(2, N):
    dia += 2*i*(i-1)//2
  dia *= 2
  # print("cheo an nhau:", dia)

  # tinh duong cheo chua Chef
  d1 = min(x, y)
  d4 = min(n-1-x, m-1-y)
  d2 = min(x, m-1-y)
  d3 = min(n-1-x, y)

  c= d1+d4+1
  dia -= c*(c-1)//2
  c= d2+d3+1
  dia -= c*(c-1)//2
  # print("cheo an nhau, tru duong cheo qua Chef:", dia)
  dia += d1*(d1-1)//2 + d4*(d4-1)//2
  dia += d2*(d2-1)//2 + d3*(d3-1)//2
  # print("cheo an nhau, final", dia)
  count = (total - hor - ver - dia)*2
  print(count)