Hướng dẫn cho Bảo vệ trang trại (C.P.VNOI 2021 LMH R5)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho \(n\) con chó và \(k\) con gà tại các tọa độ nguyên trên mặt phẳng \(Oxy\). Một con gà được gọi là an toàn nếu nó nằm trong hoặc nằm trên cạnh của một tam giác không suy biến (diện tích \(> 0\)) tạo bởi 3 con chó bất kỳ.
Yêu cầu: Đếm số lượng con gà an toàn.
Phân tích
- Điều kiện an toàn: Một điểm nằm trong ít nhất một tam giác tạo bởi tập hợp các điểm cho trước khi và chỉ khi điểm đó nằm trong hoặc nằm trên biên của Bao lồi (Convex Hull) của tập hợp điểm đó.
- Tam giác không suy biến: Để tồn tại một tam giác không suy biến, tập hợp các con chó phải có ít nhất 3 con không thẳng hàng. Nếu tất cả các con chó đều thẳng hàng, diện tích mọi tam giác tạo ra đều bằng 0, do đó không có con gà nào an toàn.
- Ràng buộc: \(n, k \leq 10^5\), tọa độ lên đến \(10^9\). Việc duyệt qua mọi tam giác (\(O(n^3)\)) hoặc kiểm tra từng con gà với từng tam giác là không khả thi.
Cách làm đơn giản (Brute Force)
Ý tưởng
Với mỗi con gà, ta duyệt qua tất cả các tổ hợp 3 con chó \((i, j, l)\). Kiểm tra xem tam giác tạo bởi 3 con chó này có diện tích khác 0 hay không. Nếu có, kiểm tra xem con gà có nằm trong tam giác đó không.
Độ phức tạp
- Thời gian: \(O(k \cdot n^3)\)
- Đánh giá: Chỉ chạy được với \(n, k\) rất nhỏ (ví dụ \(n, k \leq 100\)). Với \(n, k = 10^5\), cách này sẽ bị quá thời gian (TLE).
Code Brute Force
C++
C++
#include <bits/stdc++.h>
using namespace std;
struct Point {
long long x, y;
};
long long cross_product(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool isInside(Point a, Point b, Point c, Point p) {
long long cp1 = cross_product(a, b, p);
long long cp2 = cross_product(b, c, p);
long long cp3 = cross_product(c, a, p);
if ((cp1 >= 0 && cp2 >= 0 && cp3 >= 0) || (cp1 <= 0 && cp2 <= 0 && cp3 <= 0)) return true;
return false;
}
int main() {
int n; cin >> n;
vector<Point> dogs(n);
for (int i = 0; i < n; i++) cin >> dogs[i].x >> dogs[i].y;
int k; cin >> k;
int count = 0;
for (int i = 0; i < k; i++) {
Point chicken; cin >> chicken.x >> chicken.y;
bool safe = false;
for (int d1 = 0; d1 < n && !safe; d1++)
for (int d2 = d1 + 1; d2 < n && !safe; d2++)
for (int d3 = d2 + 1; d3 < n && !safe; d3++)
if (cross_product(dogs[d1], dogs[d2], dogs[d3]) != 0)
if (isInside(dogs[d1], dogs[d2], dogs[d3], chicken)) safe = true;
if (safe) count++;
}
cout << count;
}
Python
Python
def cross_product(a, b, c):
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
def is_inside(a, b, c, p):
cp1 = cross_product(a, b, p)
cp2 = cross_product(b, c, p)
cp3 = cross_product(c, a, p)
return (cp1 >= 0 and cp2 >= 0 and cp3 >= 0) or (cp1 <= 0 and cp2 <= 0 and cp3 <= 0)
n = int(input())
dogs = [list(map(int, input().split())) for _ in range(n)]
k = int(input())
ans = 0
for _ in range(k):
chicken = list(map(int, input().split()))
safe = False
for i in range(n):
for j in range(i + 1, n):
for l in range(j + 1, n):
if cross_product(dogs[i], dogs[j], dogs[l]) != 0:
if is_inside(dogs[i], dogs[j], dogs[l], chicken):
safe = True
break
if safe: break
if safe: break
if safe: ans += 1
print(ans)
Hướng giải quyết (Tối ưu)
Thuật toán
- Tìm Bao lồi: Sử dụng thuật toán Monotone Chain hoặc Graham Scan để tìm bao lồi của \(n\) con chó.
- Nếu bao lồi có ít hơn 3 đỉnh (tất cả các con chó thẳng hàng), diện tích mọi tam giác đều bằng 0 \(\rightarrow\) Không có con gà nào an toàn.
- Kiểm tra điểm trong đa giác lồi: Với mỗi con gà, ta cần kiểm tra nó có nằm trong bao lồi vừa tìm được hay không. Để tối ưu, ta sử dụng Tìm kiếm nhị phân trên các đỉnh của bao lồi:
- Chọn một đỉnh làm gốc (giả sử \(V_0\)).
- Các đỉnh còn lại \(V_1, V_2, \dots, V_{m-1}\) tạo thành các "hình quạt" với gốc \(V_0\).
- Một điểm \(P\) nằm trong đa giác nếu nó nằm trong góc \(\angle V_{m-1}V_0V_1\) và nằm "phía trong" cạnh \(V_iV_{i+1}\) của hình quạt chứa tia \(V_0P\).
Các bước thực hiện
- Xây dựng bao lồi \(H = \{V_0, V_1, \dots, V_{m-1}\}\) theo chiều ngược chiều kim đồng hồ.
- Với mỗi điểm \(P\):
- Kiểm tra \(P\) có nằm ngoài góc \(\angle V_{m-1}V_0V_1\) không bằng tích chéo (cross product).
- Tìm kiếm nhị phân tìm chỉ số \(i\) sao cho tia \(V_0P\) nằm giữa tia \(V_0V_i\) và \(V_0V_{i+1}\).
- Kiểm tra \(P\) có nằm bên trái hoặc trên đoạn thẳng \(V_iV_{i+1}\) không.
Độ phức tạp
- Tìm bao lồi: \(O(n \log n)\)
- Kiểm tra \(k\) điểm: \(O(k \log n)\)
- Tổng cộng: \(O((n + k) \log n)\), hoàn toàn đáp ứng được thời gian cho phép.
Code tham khảo
C++
C++
#include <bits/stdc++.h>
using namespace std;
struct Point {
long long x, y;
bool operator<(const Point& other) const {
return x < other.x || (x == other.x && y < other.y);
}
};
long long cross_product(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
vector<Point> build_convex_hull(vector<Point>& pts) {
int n = pts.size();
if (n <= 2) return pts;
sort(pts.begin(), pts.end());
vector<Point> h;
for (int i = 0; i < n; ++i) {
while (h.size() >= 2 && cross_product(h[h.size() - 2], h.back(), pts[i]) <= 0) h.pop_back();
h.push_back(pts[i]);
}
int lower_size = h.size();
for (int i = n - 2; i >= 0; --i) {
while (h.size() > lower_size && cross_product(h[h.size() - 2], h.back(), pts[i]) <= 0) h.pop_back();
h.push_back(pts[i]);
}
h.pop_back();
return h;
}
bool is_inside(const vector<Point>& hull, Point p) {
int n = hull.size();
if (n < 3) return false;
if (cross_product(hull[0], hull[1], p) < 0) return false;
if (cross_product(hull[0], hull[n - 1], p) > 0) return false;
int l = 1, r = n - 2, idx = 1;
while (l <= r) {
int mid = (l + r) / 2;
if (cross_product(hull[0], hull[mid], p) >= 0) {
idx = mid;
l = mid + 1;
} else r = mid - 1;
}
return cross_product(hull[idx], hull[idx + 1], p) >= 0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
vector<Point> dogs(n);
for (int i = 0; i < n; i++) cin >> dogs[i].x >> dogs[i].y;
vector<Point> hull = build_convex_hull(dogs);
int k, ans = 0; cin >> k;
if (hull.size() >= 3) {
for (int i = 0; i < k; i++) {
Point p; cin >> p.x >> p.y;
if (is_inside(hull, p)) ans++;
}
}
cout << ans;
return 0;
}
Python
Python
import sys
def cross_product(a, b, c):
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
def build_convex_hull(pts):
n = len(pts)
if n <= 2: return pts
pts.sort()
upper = []
for p in pts:
while len(upper) >= 2 and cross_product(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
lower = []
for p in reversed(pts):
while len(lower) >= 2 and cross_product(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
return upper[:-1] + lower[:-1]
def is_inside(hull, p):
n = len(hull)
if n < 3: return False
if cross_product(hull[0], hull[1], p) < 0: return False
if cross_product(hull[0], hull[n-1], p) > 0: return False
l, r = 1, n - 2
idx = 1
while l <= r:
mid = (l + r) // 2
if cross_product(hull[0], hull[mid], p) >= 0:
idx = mid
l = mid + 1
else:
r = mid - 1
return cross_product(hull[idx], hull[idx+1], p) >= 0
def solve():
input_data = sys.stdin.read().split()
if not input_data: return
n = int(input_data[0])
dogs = []
for i in range(n):
dogs.append((int(input_data[1 + 2*i]), int(input_data[2 + 2*i])))
hull = build_convex_hull(dogs)
k_idx = 1 + 2 * n
k = int(input_data[k_idx])
ans = 0
if len(hull) >= 3:
for i in range(k):
p = (int(input_data[k_idx + 1 + 2*i]), int(input_data[k_idx + 2 + 2*i]))
if is_inside(hull, p):
ans += 1
print(ans)
solve()
Bình luận