Hướng dẫn giải của [KSCUM VT 02] CÂU 1: Điểm nằm trong
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho tọa độ A, C (hai đỉnh đối diện của hình chữ nhật ABCD có cạnh song song với hai trục) và tọa độ hai điểm M, N. In ra số điểm nằm bên trong (không tính biên). Đề đọc từ CAU1.INP và ghi ra CAU1.OUT.
Sub 1: Kiểm tra điểm nằm trong hình chữ nhật — ~O(1)~
Chỉ có một cách hợp lý: vì B và D bị xóa tọa độ, hình chữ nhật được xác định hoàn toàn bởi A và C. Lấy xmin, xmax, ymin, ymax từ hai điểm này. Một điểm (x, y) nằm trong khi và chỉ khi xmin < x < xmax và ymin < y < ymax (dấu nhỏ hơn nghiêm ngặt, vì điểm trên biên không tính). Kiểm tra M và N rồi cộng lại. Đạt 20/20 test.
Bài chỉ có một sub vì không có cách vét cạn nào khác đáng xét: phép kiểm tra là O(1) và không cần thử các khả năng.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
long long xa, ya, xc, yc, xm, ym, xn, yn;
cin >> xa >> ya >> xc >> yc >> xm >> ym >> xn >> yn;
// ABCD la hinh chu nhat canh song song truc, A va C la hai dinh doi dien.
// Diem nam trong (khong tinh bien) khi xmin < x < xmax va ymin < y < ymax.
long long x1 = min(xa, xc), x2 = max(xa, xc);
long long y1 = min(ya, yc), y2 = max(ya, yc);
auto inside = [&](long long x, long long y) {
return x1 < x && x < x2 && y1 < y && y < y2;
};
cout << (int)inside(xm, ym) + (int)inside(xn, yn) << endl;
return 0;
}
Bình luận