trang chủ / đề bài / icpc24_mb_f

Đường thẳng độc lập

Đề bài

Mô tả

Cho tập A gồm n điểm trên mặt phẳng, điểm thứ i có tọa độ (xi,yi). Vẽ n(n−1)2 đoạn thẳng nối mọi cặp điểm. Một đường thẳng được gọi là độc lập đối với tập A nếu nó không cắt bất kỳ đoạn thẳng nào trong số này tại bất kỳ điểm nào (kể cả chỉ chạm đầu mút).

Yêu cầu: Cho m đường thẳng, hãy đếm số đường thẳng độc lập đối với tập A. Mỗi đường thẳng được cho bởi ba tham số (a,b,c) ứng với phương trình ax+by+c=0.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương T (T≤15): số bộ dữ liệu. Mỗi bộ dữ liệu có cấu trúc như sau:

  • Dòng đầu tiên chứa số nguyên n (2≤n≤105).
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi,yi (|xi|,|yi|≤108): tọa độ của điểm thứ i. Các điểm có thể trùng nhau.
  • Dòng tiếp theo chứa số nguyên dương m (m≤105).
  • m dòng cuối, dòng thứ i chứa ba số nguyên ai,bi,ci (|ai|,|bi|,|ci|≤108, ai và bi không đồng thời bằng 0): phương trình aix+biy+ci=0 của đường thẳng thứ i.

Dữ liệu ra

In ra T dòng, dòng thứ i chứa một số nguyên là số đường thẳng độc lập đối với tập A trong bộ dữ liệu thứ i.

Ràng buộc

  • 1≤T≤15
  • 2≤n≤105, 1≤m≤105
  • |xi|,|yi|≤108
  • |ai|,|bi|,|ci|≤108, (ai,bi)≠(0,0)

Ví dụ

Input Output Giải thích
1
3
0 1
1 0
-1 0
4
1 -1 0
1 0 3
0 1 0
1 0 -1
1 Ví dụ của đề gốc. Chỉ đường thẳng thứ hai (x+3=0) là độc lập. Đường y=0 chứa đoạn nối (1,0) và (−1,0), đường x−1=0 đi qua điểm (1,0).
1
4
0 0
2 0
0 2
2 2
5
1 0 -3
1 0 -2
1 1 -1
1 1 1
1 -1 3
3 Ví dụ bổ sung, tính bằng lời giải mẫu. Các đường x=3, x+y+1=0 và x−y+3=0 là độc lập; x=2 chứa cạnh của hình vuông, x+y=1 cắt đoạn nối (0,0) và (2,2).

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0