Line
Xem PDF
Điểm:
400
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(N\) đường thẳng có dạng \(Ax+By+C=0\) trên mặt phẳng tọa độ. Biết rằng không có ba đường thẳng nào cùng giao nhau ở 1 điểm. Bạn hãy tính số lượng tam giác tạo thành từ các đường thẳng. Vì kết quả có thể rất lớn, đáp số cuối cùng sẽ modulo \(10^9+7\).
Input
- Dòng đầu tiên là số nguyên dương \(N\), là số lượng đường thẳng. \((1 \leq N \leq 3 \times10^5)\)
- \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(A, B, C\) (Các giá trị tuyệt đối không vượt quá \(10^9\))
Output
- Một dòng duy nhất là số lượng tam giác tạo thành.
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(N \leq 5000\)
- Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm
Example
Test 1
Input
6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29 Output
10Note
Bình luận
Hóng sol :))
quy bài toán thành đếm số lượng bộ 3 đường thẳng (d1, d2, d3) không có cặp đường thẳng nào song song nhau
d1 : ax + by + c = 0 (1)
d2 // d1 => d2 : ax + by + c' = 0
xét (1) : => y = (-ax - c) / b
=>> d1 // d2 khi hệ số góc k1 = k2 = (-a / b)
tạo mảng k[i] = -a[i] / b[i] ( lưu ý b[i] = 0 )
sort mảng k, theo thứ tự tăng dần
dùng 2 con trỏ dễ dàng tìm được đoạn [j..i] sao cho các giá trị k của đoạn này bằng nhau ( tức các đường thẳng trong đoạn [j..i] song song nhau đôi một) , lúc này mảng k chia làm 3 phần : [1..j-1] , [j..i] và [i+1..n] , lúc này cập nhật biến res+= (j-1) x (i - j + 1) x (n - i) ( số cách lấy 3 đường thẳng không có cặp nào song song từ 3 phần này )