Cow Curling

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ điểm thuộc đội A và $N$ điểm thuộc đội B trên mặt phẳng tọa độ. Một điểm của đội B được gọi là bị chiếm bởi đội A nếu điểm đó nằm bên trong (hoặc trên biên của) bao lồi của các điểm đội A. Tương tự, một điểm của đội A bị chiếm bởi đội B nếu nằm trong bao lồi của đội B.

Tính số điểm đội A chiếm được (số điểm đội B bị bao lồi A chứa) và số điểm đội B chiếm được (số điểm đội A bị bao lồi B chứa).

Dữ liệu vào

Dòng 1: Số nguyên $N$ .
$N$ dòng tiếp theo: Tọa độ $(x_{i}, y_{i})$ của các điểm đội A.
$N$ dòng tiếp theo: Tọa độ $(x_{i}, y_{i})$ của các điểm đội B.

Dữ liệu ra

Hai số nguyên cách nhau bởi dấu cách: số điểm đội A chiếm được và số điểm đội B chiếm được.

Ràng buộc

$3 \leq N \leq 50000$
$- 40000 \leq x_{i}, y_{i} \leq 40000$
Các điểm của cùng một đội phân biệt đôi một.

Ví dụ

Input	Output	Giải thích
4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3	1 2	Bao lồi đội A là hình vuông với 4 góc (0,0),(0,2),(2,0),(2,2). Điểm (1,1) của đội B nằm trong hình vuông này. Bao lồi đội B là tứ giác (1,1),(1,10),(-10,3),(10,3). Hai điểm của đội A nằm trong bao lồi đội B.
5 0 0 0 2 0 4 0 6 0 8 0 1 0 3 0 5 0 7 0 9	4 4	Tất cả điểm đều thẳng hàng. Các điểm đội B nằm xen kẽ giữa các điểm đội A và ngược lại, mỗi đội chiếm 4 điểm.

Ghi chú

Bao lồi của một tập điểm là đa giác lồi nhỏ nhất bao gồm tất cả các điểm trong tập. Điểm nằm trên biên của bao lồi cũng được tính là bị chiếm.

Bình luận

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