Cột bò
Đề bài
Trên khu đất rộng nhà Hoàng có $n$ đống rơm, đó là thức ăn dự trữ cho chú bò vào mùa đông. Mỗi đống rơm được biểu diễn là một hình tròn trên mặt phẳng tọa độ, đống rơm thứ $i$ có tọa độ tâm là $(x_i, y_i)$ và bán kính $r_i$. Tại điểm $(a, b)$ có một cọc để cột chú bò. Vào mỗi buổi chiều tối hàng ngày, Hoàng cột chú bò của mình vào cọc bằng một sợi dây. Nếu sợi dây có độ dài $l$ thì chú bò có thể di chuyển trong vòng tròn tâm $(a, b)$ và bán kính $l$.
Yêu cầu: Hãy tìm độ dài $l$ nguyên lớn nhất sao cho chú bò không thể ăn rơm từ bất kì một đống rơm nào. Chú ý rằng, chú bò có thể ăn rơm của đống thứ $i$ nếu đường tròn tâm $(a, b)$ bán kính $l$ và đường tròn tâm $(x_i, y_i)$ bán kính $r_i$ có điểm chung.
Dữ liệu
- Dòng đầu chứa ba số nguyên $n, a, b$ ($|a|, |b| \le 10^9$);
- Dòng thứ $i$ trong $n$ dòng tiếp theo chứa ba số nguyên $x_i, y_i$ và $r_i$ ($|x_i|, |y_i|, r_i \le 10^9$).
Kết quả: một dòng ghi một số nguyên $l$ lớn nhất thỏa mãn.
Chú ý
- Có 50% số test có $n = 1$;
- Có 50% số test còn lại có $n \le 100$.
1 0 0
0 9 35Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesThì bài này là bài dễ nhất trong đề thi, có thể nói là bài cho điểm. Tuy nhiên thì vẫn sẽ có bạn không làm được bài này nếu với bạn nào không biết công thức toán học. Ở đây mình sẽ phân tích để các bạn thấy rõ quy luật làm bài này nhé.
Kiến thức 1: khoảng cách giữa 2 điểm
Thì để làm được bài này, trước tiên các bạn phải biết công thức tính khoảng cách từ điểm $A$ có hoành độ $x_A$, tung độ $y_A$ tới điểm $B$ có hoành độ $x_B$, tung độ $y_B$ trong mặt phẳng tọa độ $Oxy$, công thức đó là:
Tức là căn bậc 2 của: 2 hoành độ trừ nhau bình phương cộng 2 tung độ trừ nhau bình phương. Ví dụ nếu $A(0, 0)$ và $B(0, 9)$ tức là $x_A = 0$, $y_A = 0$, $x_B = 0$, $y_B = 9$ thì khoảng cách $AB = \sqrt{(0 - 0)^2 + (0 - 9)^2}$ $= \sqrt{81}$ $= 9$. Đây là công thức toán học từ thời cấp 3 đã học rồi nha hihi.
Kiến thức 2: khi nào 2 đường tròn chạm nhau?
Tiếp nữa các bạn phải hình dung ra khi nào thì 2 đường tròn chạm nhau, cắt nhau hay không chạm nhau. Giả sử 2 đường tròn tâm $A$ và tâm $B$ vừa chạm nhau tại điểm $X$. Điểm $X$ đó sẽ nằm trên cả 2 đường tròn. Thì ta hiểu khoảng cách từ $A$ đến $X$, tức là đoạn thẳng $AX$, chính là bán kính đường tròn tâm $A$; khoảng cách từ $B$ đến $X$, tức là đoạn thẳng $BX$, chính là bán kính đường tròn tâm $B$.
- 2 đường tròn sẽ vừa chạm nhau nếu như $AX + BX = AB$, nghĩa là tổng bán kính của 2 đường tròn bằng với khoảng cách từ tâm đường tròn này tới tâm đường tròn kia.
- 2 đường tròn sẽ cắt nhau nếu $AX + BX > AB$, nghĩa là tổng bán kính của 2 đường tròn lớn hơn khoảng cách từ tâm đường tròn này tới tâm đường tròn kia.
- 2 đường tròn sẽ không thể chạm hay cắt nhau (tức là nằm rời rạc nhau) nếu $AX + BX < AB$, nghĩa là tổng bán kính của 2 đường tròn nhỏ hơn khoảng cách từ tâm đường tròn này tới tâm đường tròn kia.
Các bạn thử vẽ ra giấy hay tưởng tượng thử xem có đúng quy luật như vậy không ^^ Cái này cũng là kiến thức toán cấp 2 hay cấp 3 mình không nhớ nhưng chắc chắn là có được học rồi.
50%Trường hợp chỉ có 1 bó cỏ
Vậy quay lại bài này, bây giờ trước tiên ta hãy giả định rằng chỉ có 1 bó cỏ duy nhất, tức là 50% test case trong bài này sẽ chỉ có 1 bó cỏ duy nhất. Ta thử suy nghĩ giải quyết trường hợp này trước, từ đó ta sẽ nhìn ra quy luật để xử lý tổng quát trong trường hợp có nhiều hơn 1 bó cỏ, tức là 50% test case còn lại.
Thì các bạn xem nhé, nếu trong trường hợp có 1 bó cỏ, bán kính tức là chiều dài dây cột là $L$ phải lớn nhất là bao nhiêu nhưng bò không thể ăn được cỏ. Vậy đơn giản là ta cứ tính ra trường hợp nếu bò vừa đủ để ăn được cỏ khi đó $L$ là bao nhiêu? Thì như thế chỉ cần giảm $L$ đi 1 đơn vị là nó sẽ thỏa mãn điều kiện vừa là lớn nhất có thể nhưng bò không thể ăn cỏ được.
Thì với trường hợp vừa đủ để cho bò ăn cỏ, nghĩa là đường tròn tâm $(a, b)$ của bò sẽ vừa đủ để tiếp xúc với đường tròn tâm $(x, y)$ của bó cỏ. Ta có thể tính khoảng cách giữa 2 tâm, gọi khoảng cách đó là $D$, thì như thế ta sẽ hiểu để 2 đường tròn tiếp xúc với nhau nghĩa là:
với $R$ là bán kính của bó cỏ, $L$ là bán kính của đường tròn có tâm là vị trí cọc cột bò, $D$ là khoảng cách giữa 2 tâm. Lúc này ta đã có $D$, và ta cũng có $R$ là bán kính các bó cỏ đề cho sẵn, lúc này ta có thể tính ra $L$ là chiều dài sợi dây cột bò.
Như ví dụ đề đưa ra, cọc cột bò có tọa độ $(0, 0)$. Bó cỏ có tọa độ $(0, 9)$. Bán kính của bó cỏ $R = 3$. Như thế khoảng cách $D = \sqrt{(0 - 0)^2 + (0 - 9)^2}$ $= \sqrt{81}$ $= 9$. Ta tìm ra $L = D - R = 9 - 3 = 6$. Vậy nghĩa là chiều dài dây cột bò cần dài 6 là bò vừa đủ ăn được cỏ. Trong khi đó ta không muốn bò ăn cỏ nhưng muốn $L$ làm sao lớn nhất có thể. Vậy đơn giản lúc này giảm chiều dài $L$ xuống 1 đơn vị, tức $L = 6 - 1 = 5$, thì bò sẽ không ăn được cỏ và lúc này đây chiều dài $L$ là lớn nhất có thể. Đáp án in ra 5.
BẫyCẩn thận khi L là số thực
Cũng một lưu ý để tránh các bạn dễ sai chỗ này: giả sử trong tình huống trên, nếu cọc cột bò có tọa độ là $(2, 0)$. Bó cỏ vẫn giữ nguyên thông tin như vậy. Khi đó $D = \sqrt{2^2 + 9^2} = \sqrt{85} = 9.2195$. Vậy $L = D - R = 9.2195 - 3 = 6.2195$.
Nếu như thế lúc này ta cứ mặc định chiều dài dây cột bò là $L$ phải là số nguyên, thì khi nhận kết quả 6.2195 gán sang thì $L$ chỉ nhận được phần nguyên là 6, và nếu ta giảm đi 1 đơn vị thì $L = 5$. Như thế sẽ không đúng, vì bản chất trong tình huống này khi thực sự chiều dài $L$ là 6.2195 thì chỉ cần lấy phần nguyên tức là 6 thì bò cũng sẽ không thể ăn được cỏ rồi. Vì $L + R = 6 + 3 = 9$ trong khi phải là 9.2195 thì nó mới đủ ăn cỏ.
| Cọc | D | L = D − R (số thực) | Cứ lấy phần nguyên rồi trừ 1 | Đúng |
|---|---|---|---|---|
| (0, 0) | 9.0000 | 6.0000 | 5 | 5 |
| (2, 0) | 9.2195 | 6.2195 | 5 | 6 |
- nếu số thực $L$ không có phần dư sau dấu chấm, tức là nó là 6.0000 chẳng hạn, thì khi ép kiểu lấy phần nguyên ta lấy được 6 và giảm xuống 1 đơn vị còn 5;
- còn nếu kiểm tra thấy số thực $L$ có phần dư sau dấu chấm, ví dụ 6.2195, thì ta chỉ ép kiểu lấy phần nguyên là 6 chứ không có giảm xuống 1 đơn vị.
100%Trường hợp nhiều bó cỏ
Rồi thì trường hợp như trên phân tích là với 1 bó cỏ. Vậy trong trường hợp có nhiều bó cỏ thì sao? Cụ thể có thể lên đến tối đa 100 bó cỏ. Lúc này ta sẽ hiểu cần tìm ra chiều dài $L$ sao cho bò không thể ăn được cỏ từ bất kỳ 1 bó nào.
Thì cái tư duy để xử lý chỗ này rất đơn giản thôi: ta hãy xét qua đủ $N$ bó cỏ, với mỗi bó cỏ ta đi tính ra xem để bò có thể ăn được bó cỏ đó thì cần chiều dài $L$ bao nhiêu? Và ta xem trong tất cả $N$ trường hợp thì chiều dài $L$ ít nhất cần là bao nhiêu? Và đáp án chính là trường hợp $L$ ít nhất đó, ta sẽ giảm $L$ để nó không thể ăn được bó cỏ trong trường hợp ít nhất đó thì đảm bảo mọi bó cỏ khác nó cũng sẽ không ăn được.
Ví dụ ta có 3 bó cỏ, để ăn được bó cỏ 1 thì bò cần $L = 8$, ăn được bó cỏ 2 thì bò cần $L = 5$, ăn được bó cỏ 3 thì bò cần $L = 3$:
Vậy ta căn cứ theo trường hợp $L$ bé nhất tức là $L = 3$. Vậy đáp án sẽ là $L = 2$ thì bò sẽ không thể ăn được bất kỳ bó cỏ nào trong 3 bó, quy luật thực tế đơn giản như vậy thôi.
Em nhập tọa độ cọc và các đống rơm (dạng x y r, cách nhau bởi dấu phẩy) rồi bấm Tiếp để xem với từng đống, dây dài bao nhiêu thì bò vừa chạm tới, và đáp án được chốt thế nào:
Source code
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, a, b;
cin >> n >> a >> b;
double Min = DBL_MAX;
while(n--){
long long x, y, r;
cin >> x >> y >> r;
Min = min(Min, sqrt((x - a) * (x - a) + (y - b) * (y - b)) - r);
}
long long res = Min;
if(Min == res){
res--;
}
cout << res;
return 0;
}import math
import sys
n, a, b = map(int, sys.stdin.readline().split())
Min = float('inf')
for _ in range(n):
x, y, r = map(int, sys.stdin.readline().split())
Min = min(Min, math.sqrt((x - a) * (x - a) + (y - b) * (y - b)) - r)
res = int(Min)
if Min == res:
res -= 1
print(res)Giải thích một số chỗ trong code
- 2 dòng đầu tiên của hàm main (
ios::sync_with_stdio(0); cin.tie(0);) giúp tăng tốc nhập xuất của C++. Mặc địnhcin/coutđược đồng bộ vớiscanf/printfcủa C nên chạy khá chậm. Dòng thứ nhất tắt sự đồng bộ này, dòng thứ hai bỏ việc tự động xả bộ đệmcoutmỗi lầncinđọc dữ liệu, nhờ vậy tốc độ nhập xuất củacin/coutnhanh ngang ngửa C. Nên 1 kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta hãy nên để 2 dòng này vào để chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé. double Min = DBL_MAX;ThìDBL_MAXlà giá trị lớn nhất của kiểu dữ liệudouble. Ta khởi tạo như vậy để đảm bảo mọi giá trị lần đầu tiên khi so sánh với nó sẽ luôn thỏa nhỏ hơnMinmà cập nhật lạiMin= giá trị đó. Bình thường phải cần thư việncfloatđể gọi ra các giới hạn MIN, MAX của kiểu số thực (với kiểu số nguyên làclimits), nhưng do ta đã include thư việnbits/stdc++.hnó bao chứa các thư viện khác nên không cần gọi.while(n--)nghĩa là vòng lặp sẽ lặp $n$ lần. Viết thế kia là viết gọn, viết đầy đủ sẽ là:while(n != 0) { n--; ... }, tức là $n$ sẽ lặp đến khi nào về 0 thì dừng và mỗi lần lặp sẽ giảm đi 1 đơn vị.- Hàm
min(a, b)sẽ trả về giá trị nhỏ nhất giữa 2 tham số $a$, $b$ truyền vào. Hàm này được hỗ trợ trong thư viện giải thuật (algorithm). Tuy nhiên do ta đang include<bits/stdc++.h>thì nó đã bao chứa hết các thư viện khác vì thế chỉ cần 1 mình thư viện này là đủ, nhưng nếu bạn nào muốn rõ ràng thì phải gọi#include <algorithm>thì mới sử dụng đượcstd::minhaystd::maxnày nhé. Hay như trình biên dịch MSVC (Visual Studio) thì không hỗ trợ thư việnbits/stdc++.hnên các bạn muốn dùng cái gì là phải khai báo riêng thư viện của nó, nhớ phải khai báo đúng thư viện thì mới dùng được hàm này nha. Min = min(Min, sqrt((x - a) * (x - a) + (y - b) * (y - b)) - r);Nghĩa là đi tính ra giá trị của $L = D - R$ với $D$ =sqrt((x - a) * (x - a) + (y - b) * (y - b)), rồi so sánh vớiMinvà cập nhật lạiMinđể sau cùngMinchính là giá trị $L$ nhỏ nhất sau khi xét qua đủ $N$ bó cỏ. Từ đó ta gán giá trịMinđang có kiểudoubleđó sang biếnreskiểulong long(số nguyên), rồi kiểm tra nếu sau khi gán xong màMinvẫn bằngres, nghĩa là số thựcMinđó không có phần sau dấu chấm, ví dụMin= 6.0000, như thế ta phải giảmresxuống 1 đơn vị. Còn nếu điều kiện đó không thỏa nghĩa là số thựcMincó phần sau dấu chấm, như thế ta chỉ lấy phần nguyên củaMinchứ không có giảm 1 đơn vị. Kết quả xuất rares.
Đánh giá độ phức tạp
- Độ phức tạp không gian (Space Complexity): $O(1)$.
- Độ phức tạp thời gian (Time Complexity): $O(N)$ với $N$ là số lượng bó cỏ.
Với độ phức tạp như trên thì chắc chắn đây là cách làm tối ưu nhất cho bài này nha các bạn, vì nó chỉ là bước đọc dữ liệu từ input vào và đọc xong thì xuất ra kết quả luôn. Mọi bài thì tối thiểu nhất lúc nào cũng phải đọc dữ liệu input vào xong thì mới đi xử lý, nên ở đây đọc dữ liệu vào xong thì ta đã có luôn đáp án, vì ta đi xử lý ngay trong quá trình đọc dữ liệu input, nên đây là cách làm tối ưu nhất rồi.
Và với độ phức tạp $O(N)$ này tức là vòng lặp chạy $N$ lần, như đề bài cho $N$ tối đa là 100 vì thế nghĩa là vòng lặp chạy trong trường hợp xấu nhất là 100 lần, và như thế ta yên tâm sẽ không thể bị TLE được vì còn quá nhỏ so với ngưỡng giới hạn $(3 \div 5) \times 10^7$ hay cao lắm là $10^8$.
Mở rộng: khi tọa độ rất lớn, số thực có thể "lừa" ta
Code ở trên đã đủ AC bài này. Tuy nhiên vì đề cho tọa độ lên đến $10^9$ nên khoảng cách giữa 2 tâm có thể lên tới khoảng $2.8 \times 10^9$, trong khi kiểu double chỉ giữ được khoảng 15–16 chữ số có nghĩa. Khi đó những phần thập phân cực nhỏ sẽ bị làm tròn mất, và phép kiểm tra "$L$ có phần dư sau dấu chấm hay không" có thể bị sai. Bạn nào thích tìm hiểu sâu thì xem thử test này:
1 -1000000000 0
1000000000 1 119999999991999999998Ở test này $D^2 = (2 \times 10^9)^2 + 1^2$ $= 4 \times 10^{18} + 1$, nên $D$ lớn hơn $2 \times 10^9$ một chút xíu (khoảng $2.5 \times 10^{-10}$), tức là $D$ có phần dư, đáng lẽ không được trừ 1. Nhưng phần dư nhỏ xíu đó double không lưu nổi nên sqrt trả về đúng tròn $2000000000.0$, code tưởng không có phần dư nên trừ 1 và in ra thiếu 1 đơn vị.
Cách khắc phục triệt để là không dùng số thực nữa, làm hoàn toàn trên số nguyên: tính $D^2$ bằng số nguyên (tối đa $8 \times 10^{18}$, vẫn vừa kiểu long long), rồi tìm $s$ là phần nguyên của $\sqrt{D^2}$. Nếu $s^2 = D^2$ thì $D$ là số nguyên, ta lấy $L = s - 1 - R$; ngược lại $D$ có phần dư, ta lấy $L = s - R$. Đúng y như quy tắc chốt ở trên, chỉ là giờ kiểm tra "có phần dư hay không" một cách chính xác tuyệt đối.
Xem code tính toàn bộ bằng số nguyên
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, a, b;
cin >> n >> a >> b;
long long res = LLONG_MAX;
while(n--){
long long x, y, r;
cin >> x >> y >> r;
long long D2 = (x - a) * (x - a) + (y - b) * (y - b); // D^2, tối đa 8*10^18
long long s = sqrtl(D2); // phần nguyên của D
while(s * s > D2) s--; // chỉnh lại cho chính xác
while((s + 1) * (s + 1) <= D2) s++;
long long L;
if(s * s == D2){
L = s - 1 - r; // D là số nguyên: L + r phải nhỏ hơn hẳn D
}
else{
L = s - r; // D có phần thập phân: lấy luôn phần nguyên
}
res = min(res, L);
}
cout << res;
return 0;
}import math
import sys
n, a, b = map(int, sys.stdin.readline().split())
res = float('inf')
for _ in range(n):
x, y, r = map(int, sys.stdin.readline().split())
D2 = (x - a) * (x - a) + (y - b) * (y - b) # D^2, số nguyên chính xác tuyệt đối
s = math.isqrt(D2) # phần nguyên của D
if s * s == D2:
L = s - 1 - r # D là số nguyên: L + r phải nhỏ hơn hẳn D
else:
L = s - r # D có phần thập phân: lấy luôn phần nguyên
res = min(res, L)
print(res)