Đường Dây Điện

Điểm: 6,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Trên mặt phẳng tọa độ cho $n$ cột điện, cột thứ $i$ đặt tại điểm $(x_{i}, y_{i})$ . Mọi cặp cột điện đều được nối với nhau bởi một dây dẫn là đường thẳng vô hạn về hai phía đi qua hai cột. Nếu có nhiều hơn hai cột cùng nằm trên một đường thẳng thì chúng dùng chung một dây duy nhất (tức là mỗi đường thẳng chỉ được tính một lần dù có bao nhiêu cột nằm trên đó).

Hãy đếm số cặp dây dẫn giao nhau (cắt nhau tại đúng một điểm trên mặt phẳng). Hai dây song song hoặc trùng nhau không được tính.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số cột điện.
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ , $y_{i}$ — tọa độ cột điện thứ $i$ . Đảm bảo tất cả $n$ điểm đôi một phân biệt.

Dữ liệu ra

In ra một số nguyên duy nhất là số cặp dây dẫn giao nhau.

Ràng buộc

$2 \leq n \leq 1000$
$- 10^{4} \leq x_{i}, y_{i} \leq 10^{4}$
Các điểm đôi một phân biệt.

Ví dụ

Input	Output	Giải thích
4 0 0 1 1 0 3 1 2	14	Có $6$ đường thẳng phân biệt đi qua các cặp điểm, tạo thành $14$ cặp giao nhau.
4 0 0 0 2 0 4 2 0	6	Ba điểm $(0, 0)$ , $(0, 2)$ , $(0, 4)$ thẳng hàng nên chung một dây. Tổng cộng có $4$ dây phân biệt, có $6$ cặp giao nhau.
3 -1 -1 1 0 3 1	0	Ba điểm thẳng hàng nên chỉ có $1$ dây duy nhất, không có cặp giao nào.

Bình luận

Không có bình luận tại thời điểm này.