trang chủ / bài tập / pwrlines

Đường Dây Điện

Đề bài

Mô tả

Trên mặt phẳng tọa độ cho n cột điện, cột thứ i đặt tại điểm (xi,yi). 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 xi, yi — 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

  • 2n1000
  • 104xi,yi104
  • 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 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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0