Đoạn thẳng

View as PDF

Submit solution

Points: 1.36 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
TCO 2010
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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ố ~x_1~, ..., ~x_N~ theo công thức:

~x_1 = xFirst~

~x_{k} = (x_{k - 1} \times xProd + xAdd) \bmod xMod~ với ~2 \leq k \leq N~ (lưu ý tràn số)

Dãy số ~y_1~, ..., yN được sinh tương tự

~N~ điểm trên mặt phẳng là ~(x_1~, ~y_1~), ~(x_2~, ~y_2~), ..., (~x_N~, ~y_N~)

Input

  • ~9~ số nguyên ~N~, ~xFirst~, ~xAdd~, ~xProd~, ~xMod~, ~yFirst~, ~yAdd~, ~yProd~, yMod. Giới hạn:
  • ~2 \leq N \leq 1200~
  • ~0 < xMod,\ yMod \leq 10^{6}~
  • ~0 \leq xFirst,\ xAdd,\ xProd < xMod~
  • ~0 \leq yFirst,\ yAdd,\ yProd < yMod~

Output

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

Sample Input

5
1
1
1
3
4
3
2
5

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.