Xin ý tưởng bài toán đếm số tam giác mà có toạ độ trọng tâm là số nguyên

#1
#2

Diện tích bằng 0 thì tức 3 điểm thẳng hàng, vậy sao là tam giác được nhỉ. :thinking:

2 Likes
#3

Chia theo modulo rồi dùng đếm tổ hợp bạn.

5 Likes
#4

nếu ko cho thẳng hàng thì chỉ có cách O(n^3) thôi: xét lần lượt 3 điểm trong n điểm xem có phải là tam giác hay ko =] chưa tính trọng tâm có phải là số nguyên hay ko mà đã mất O(n^3) rồi

3 Likes
#5

cho thẳng hàng rồi thì các điểm được chia thành 9 nhóm đánh số từ 0 tới 8 :V điểm (x,y) cho vào nhóm x%3*3 + y%3. Ví dụ điểm (1000, 2000) là nhóm 1000%3*3 + 2000%3 = nhóm 5.

nhóm 0 là nhóm có x chia 3 dư 0, y chia 3 dư 0
nhóm 1 là nhóm có x chia 3 dư 0, y chia 3 dư 1
nhóm 2 là nhóm có x chia 3 dư 0, y chia 3 dư 2
nhóm 3 là nhóm có x chia 3 dư 1, y chia 3 dư 0
nhóm 4 là nhóm có x chia 3 dư 1, y chia 3 dư 1
nhóm 5 là nhóm có x chia 3 dư 1, y chia 3 dư 2
nhóm 6 là nhóm có x chia 3 dư 2, y chia 3 dư 0
nhóm 7 là nhóm có x chia 3 dư 2, y chia 3 dư 1
nhóm 8 là nhóm có x chia 3 dư 2, y chia 3 dư 2

rồi sau đó xét 3 điểm trong 9 nhóm này: (u, v, w) sao cho u <= v <= w. Ví dụ chọn 3 điểm từ nhóm 0, nhóm 0, và nhóm 0 thì 3 điểm này là “tam giác” loại (0,0,0). Nhóm 0 là nhóm có x chia hết cho 3 và y chia hết cho 3. Vậy tam giác nằm trong loại 0,0,0) cũng sẽ có tổng x chia hết cho 3 và tổng y chia hết cho 3. Vậy các tam giác tạo từ nhóm (0,0,0) là hợp lệ :V

tương tự với các điểm lấy từ các nhóm (4,4,4) (nhóm 4 là nhóm các điểm có x, y chia 3 dư 1), (8,8,8) (nhóm 4 là nhóm các điểm có x, y chia 3 dư 2), (0,4,8) v.v… :V

xét 9x9x9 = 729 các tam giác loại (u,v,w), xét loại nào hợp lệ rồi tính mỗi loại tam giác có bao nhiêu tam giác rồi cộng vào kết quả cuối cùng :V

chia nhóm cho n điểm tốn O(n)
xét 729 trường hợp, mỗi trường hợp tốn O(1), tổng cộng vẫn là O(1)
vậy đpt chỉ là O(n) :V :V

3 Likes
#6

Có 4 tổ hợp trong Z/3Z vị chi là 16 tổ hợp cần xét :sweat:

2 Likes
#7

ai biết đâu, duyệt trâu 729 trường hợp luôn cho chắc =]] cũng O(1) thôi

2 Likes
#8

Chia các điểm thành 9 nhóm :smiley: sau đó áp 4^2 = 16 pattern vào.
(0,0,0)
(0,1,2)
(1,1,1)
(2,2,2)

3 Likes
#9

hình như tới 21 lận?:

for u in range(9):
    for v in range(u, 9):
        for w in range(v, 9):
            if (u//3 + v//3 + w//3) % 3 == 0 and (u%3 + v%3 + w%3) % 3 == 0:
                print((u,v,w,))

(0, 0, 0)
(0, 1, 2)
(0, 3, 6)
(0, 4, 8)
(0, 5, 7)
(1, 1, 1)
(1, 3, 8)
(1, 4, 7)
(1, 5, 6)
(2, 2, 2)
(2, 3, 7)
(2, 4, 6)
(2, 5, 8)
(3, 3, 3)
(3, 4, 5)
(4, 4, 4)
(5, 5, 5)
(6, 6, 6)
(6, 7, 8)
(7, 7, 7)
(8, 8, 8)

vậy xét 21 th này thôi thay vì 729, rồi viết thêm code tính tổ hợp là xong mà =]

2 Likes
#10

Chia 3 thì xét Z/3Z thôi :sweat:

#11

3/Z3 là sao :V :V đã có máy tính chạy trâu cần gì toán nữa =]
lạ ở chỗ ko có loại nào 2 điểm thuộc 1 nhóm và 1 điểm thuộc nhóm khác nhỉ :V 3 điểm 1 nhóm hoặc 3 điểm 3 nhóm, vậy càng dễ tính nữa :V

return 1 phát luôn =]

return
f[0]*f[1]*f[2] + 
f[0]*f[3]*f[6] + 
f[0]*f[4]*f[8] + 
f[0]*f[5]*f[7] + 
f[1]*f[3]*f[8] + 
f[1]*f[4]*f[7] + 
f[1]*f[5]*f[6] + 
f[2]*f[3]*f[7] + 
f[2]*f[4]*f[6] + 
f[2]*f[5]*f[8] + 
f[3]*f[4]*f[5] + 
f[6]*f[7]*f[8] + 
f[0]*(f[0]-1)*(f[0]-2)/6 + 
f[1]*(f[1]-1)*(f[1]-2)/6 + 
f[2]*(f[2]-1)*(f[2]-2)/6 + 
f[3]*(f[3]-1)*(f[3]-2)/6 + 
f[4]*(f[4]-1)*(f[4]-2)/6 + 
f[5]*(f[5]-1)*(f[5]-2)/6 + 
f[6]*(f[6]-1)*(f[6]-2)/6 + 
f[7]*(f[7]-1)*(f[7]-2)/6 + 
f[8]*(f[8]-1)*(f[8]-2)/6;
3 Likes
#13

cái code ruby thì phải :V nhìn ko hiểu gì

#14 
h = [[0, 0, 0] * 3]
$stdin.each_line do |line|
   x, y = line.split.map(:to_i)
   h[x%3][y%3] += 1
end
p = [[0,0,0],[0,1,2],[1,1,1],[2,2,2]]
KW_DEF = [3,3]
print p.product(p).map (v) -> {old,count=KW_DEF,1; v[0].zip(v[1]).inject(1)(p,w) -> {
   if w != old then old,count = w,1; return p * h[w[0]][w[1]]
   else count += 1; return p * (h[w[0]][w[1]] - count+1)/count
   end }
}.sum
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?