Đ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) % 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.