Giải bài trực tuyến

Cho N điểm trên mặt phẳng sao cho không có 3 điểm nào đoạn thẳng.

Yêu cầu: hãy đếm số cặp đoạn thẳng thỏa mãn 2 điều kiện:

• Đầu mút của chúng thuộc N điểm đã cho, và 2 đoạn thẳng không có chung đầu mút

• 2 đoạn thẳng cắt nhau.

Để giảm kích thước input, dữ liệu được đưa vào như sau:

Sinh ra dãy số x1,…,xN theo công thức:

x1 = xFirst

x(k) = (x(k – 1) * xProd + xAdd) % xMod với 2 <= k <= N (lưu ý tràn số)

Dãy số y1,…,yN được sinh tương tự

N điểm trên mặt phẳng là (x1,y1), (x2,y2), …, (xN, yN)

Input :

• 9 số nguyên N, xFirst, xAdd, xProd, xMod, yFirst, yAdd, yProd, yMod. Giới hạn :

• 2 <= N <= 1200

• 0 < xMod, yMod <= 10^6

• 0 <= xFirst,xAdd,xProd < xMod

• 0 <= yFirst,yAdd,yProd < yMod

Output :

• Đưa ra số cặp đoạn thẳng cắt nhau như trong đề bài

Example

Minh họa cho test ví dụ đầu tiên