trang chủ / đề bài / icpc24_nat_e

Loại bỏ cạnh

Đề bài

Mô tả

Cho một đồ thị vô hướng, đơn, liên thông và phẳng gồm n đỉnh và m cạnh. Một đồ thị là phẳng nếu có thể vẽ nó trên mặt phẳng sao cho các cạnh chỉ cắt nhau tại các đầu mút. Ở bài này, đồ thị được cho kèm một cách vẽ như vậy: mỗi đỉnh là một điểm có tọa độ nguyên và mỗi cạnh là đoạn thẳng nối hai đỉnh của nó.

Hãy đếm số cách chọn đúng 3 cạnh khác nhau để xóa khỏi đồ thị sao cho đồ thị còn lại không còn liên thông.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số bộ test t (1≤t≤3·105). Tiếp theo là mô tả các bộ test.

  • Dòng đầu tiên của mỗi bộ test chứa hai số nguyên n và m (3≤n,m≤3·105): số đỉnh và số cạnh của đồ thị.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi và yi (|xi|,|yi|≤109): tọa độ của đỉnh thứ i.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (1≤u,v≤n, u≠v) cho biết có một cạnh nối đỉnh u và đỉnh v (vẽ bằng đoạn thẳng).

Dữ liệu đảm bảo:

  • đồ thị liên thông,
  • không có hai điểm nào trùng tọa độ,
  • không có hai cạnh nào cắt nhau ngoại trừ tại đầu mút chung (nếu có),
  • mỗi cặp điểm được nối bởi tối đa một cạnh,
  • tổng n trên tất cả các bộ test không vượt quá 3·105,
  • tổng m trên tất cả các bộ test không vượt quá 3·105.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên là số cách chọn đúng 3 cạnh để xóa làm đồ thị mất liên thông.

Ràng buộc

  • 1≤t≤3·105
  • 3≤n,m≤3·105; tổng n và tổng m trên tất cả các bộ test đều không vượt quá 3·105
  • |xi|,|yi|≤109

Ví dụ

Input Output Giải thích
1
8 10
1 1
4 1
4 4
1 4
2 2
3 2
3 3
2 3
1 2
2 3
3 4
4 1
5 6
7 8
1 5
2 6
3 7
4 8
64 Đồ thị gồm hình vuông ngoài 1,2,3,4, hai cạnh 5-6 và 7-8 bên trong, và bốn cạnh nối đỉnh i với đỉnh i+4. Ví dụ, xóa các cạnh thứ 3, 4 và 9 (cạnh 3-4, 4-1, 3-7) tách nhóm đỉnh 4,7,8 khỏi phần còn lại.
3
3 3
0 0
2 0
0 2
1 2
2 3
3 1
5 4
0 0
1 0
2 0
3 0
0 5
1 2
2 3
3 4
1 5
4 6
0 0
2 0
1 1
1 3
1 2
1 3
2 3
1 4
2 4
3 4
1
4
4
Bộ test thứ nhất: phải xóa cả ba cạnh của tam giác. Bộ test thứ hai: đồ thị là một cây, xóa bất kỳ 3 trong 4 cạnh đều được. Bộ test thứ ba: đồ thị đầy đủ 4 đỉnh, chỉ có 4 cách là xóa ba cạnh của cùng một đỉnh.

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