Toạ độ gần hơn

Nguồn: CLUE OJ Độ khó: Dễ Rẽ nhánh Hình học

Đề bài

Trên mặt phẳng toạ độ $Oxy$ cho hai điểm $A(x, y)$ và $B(u, v)$ với toạ độ là các số nguyên. Hãy cho biết điểm nào gần gốc toạ độ $O(0, 0)$ hơn.

Gợi ý: khoảng cách từ điểm $(x, y)$ tới gốc toạ độ là $d = \sqrt{x^2 + y^2}$.

Dữ liệu vào:

Một dòng gồm 4 số nguyên $x, y, u, v$.

Kết quả:

• In ra A nếu điểm $A$ gần gốc toạ độ hơn.
• In ra B nếu điểm $B$ gần gốc toạ độ hơn.
• In ra BANG NHAU nếu hai điểm cách gốc toạ độ bằng nhau.

Giới hạn:

• $|x|, |y|, |u|, |v| \le 10^9$

Subtask:

• Subtask 1 (40% số điểm): $|x|, |y|, |u|, |v| \le 1000$.
• Subtask 2 (60% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

4 4 -4 -4

Ví dụ 1 – output

BANG NHAU

Ví dụ 2 – input

1 1 2 2

Ví dụ 2 – output

A

Ví dụ 3 – input

3 3 0 0

Ví dụ 3 – output

B

Nguồn: phỏng theo bài "Toạ độ gần hơn" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Đề gợi ý dùng $d = \sqrt{x^2 + y^2}$, nhưng thật ra không cần lấy căn: so sánh hai khoảng cách cũng là so sánh bình phương của chúng – vừa nhanh, vừa tránh được sai số số thực khi toạ độ tới $10^9$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngso bình phươngLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8 thuộc subtask 1 (toạ độ $\le 1000$), test 9–20 có toạ độ tới $10^9$.

Test	Nội dung kiểm tra
1–8	Số nhỏ: hai điểm cách đều, điểm trùng gốc, toạ độ âm, tam giác 3-4-5
9–12	Toạ độ cỡ $10^9$, bình phương khoảng cách chênh nhau đúng 1 đơn vị (hoặc bằng nhau): sqrt / double không phân biệt được
13–20	Toạ độ tới $\pm 10^9$: bình phương tới $2 \cdot 10^{18}$, tràn int

Ý tưởngSo sánh bình phương khoảng cách

Khoảng cách luôn không âm, nên $d_A < d_B \iff d_A^2 < d_B^2$. Vậy chỉ cần so sánh

$$D_A = x^2 + y^2 \quad \text{và} \quad D_B = u^2 + v^2.$$

Vì sao không dùng sqrt?

Với toạ độ cỡ $10^9$, $D_A$ và $D_B$ cỡ $10^{18}$. Hai số chênh nhau 1 đơn vị, sau khi lấy căn chỉ chênh nhau khoảng $5 \cdot 10^{-10}$ – double không còn phân biệt được. Dùng số nguyên long long thì so sánh chính xác tuyệt đối.

Em nhập toạ độ hai điểm rồi bấm Tiếp:

x = y = u = v =

Ví dụ nhanh:

Lời giảiHai bình phương + if / else if / else

Tính $D_A$, $D_B$ bằng long long rồi rẽ 3 nhánh.

C++▶ Chạy tay từng dòng codeTính bình phương khoảng cách của A và B rồi so sánh.

Dữ liệu vào (stdin) – sửa thoải mái4 4 -4 -4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. $x^2 + y^2 \le 2 \cdot 10^{18}$ vẫn nằm trong giới hạn long long (khoảng $9{,}2 \cdot 10^{18}$).
2. Kỹ thuật "so sánh bình phương thay vì so sánh căn" dùng rất nhiều trong hình học tính toán.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.005s. Bản Python đúng 20/20 test, chạy lâu nhất 0.032s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Tính khoảng cách bằng sqrt (số thực) rồi so sánh	17/20	sai test 10, 12, 19
Dùng int	18/20	sai test 14, 20
So sánh $|x| + |y|$ (khoảng cách "Manhattan", sai công thức)	11/20	sai test 5, 6, 7, 8, 9, 10, 11, 12, 19

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.005s	Full điểm
	Python	20/20	0.032s	Full điểm
Dùng sqrt	C++	17/20	–	Mất 3 test
Dùng int	C++	18/20	–	Mất 2 test
Sai công thức	C++	11/20	–	Mất 9 test

Ghi chú của mình: chỉ cần biết "so sánh hai số không âm cũng là so sánh bình phương của chúng" là bỏ được phép căn – và bỏ luôn mọi rắc rối về sai số.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇