Số hình tam giác có N điểm bên trong

Question

Cho một số điểm trong mặt phẳng (tối đa 500 điểm), không có 3 chốt. Chúng ta phải xác định số tam giác có đỉnh là từ các điểm đã cho và chứa chính xác N điểm bên trong chúng. Làm thế nào để giải quyết vấn đề này hiệu quả? Thuật toán O (n^4) ngây thơ quá chậm. Bất kỳ cách tiếp cận tốt hơn?

Answer 1

Bạn có thể thử nghĩ về tam giác như giao điểm của ba nửa không gian. Để tìm số điểm bên trong tam giác A, B, C trước tiên hãy xem xét tập các điểm trên một bên của đường vô hạn theo hướng AB. Hãy để các bộ này L (AB) và R (AB) cho các điểm bên trái và bên phải. Tương tự bạn cũng giống với hai cạnh khác và xây dựng bộ L (AC) và R (AC) và đặt L (BC) và R (BC).

Vì vậy, số điểm trong ABC sẽ là số điểm trong giao điểm của L (AB), L (AC) và L (BC). (Bạn có thể muốn xem xét R (AB) thay vì tùy thuộc vào hướng của tam giác).

Bây giờ, nếu chúng tôi muốn xem xét toàn bộ 500 điểm. Đầu tiên lấy tất cả các cặp điểm AB và xây dựng các bộ L (AB) và R (AB). Thao tác này sẽ thực hiện các hoạt động O (n^3).

Tiếp theo, chúng tôi kiểm tra tất cả các hình tam giác và tìm giao điểm của ba bộ. Nếu chúng ta sử dụng một số cấu trúc bảng băm cho các bộ thì để tìm các điểm giao nhau giống như một tra cứu có thể bắt đầu. Nếu L (AB) có các phần tử l, L (AC) có các phần tử m và phần tử L (BC) n. Nói l> m> n. Đối với mỗi điểm trong L (BC), chúng ta cần thực hiện tra cứu trong L (AC) và L (BC) sao cho tối đa 2n tra cứu có thể bắt đầu.

Có thể nhanh hơn để xem xét bảng tra cứu hình học. Chia toàn bộ miền của bạn thành lưới thô nói một lưới 10 x 10. Sau đó chúng ta có thể đặt mỗi điểm vào một tập G (i, j). Sau đó chúng ta có thể chia bộ L (AB) thành mỗi ô lưới. Nói gọi các bộ này L (AB, i, j) và R (AB, i, j). Trong thử nghiệm cho các giao lộ tập luyện đầu tiên mà các tế bào lưới nằm trong giao lộ. Điều này làm giảm đáng kể không gian tìm kiếm và khi mỗi bộ L (AB, i, j) chứa ít thành viên hơn, sẽ có ít tra cứu có thể tìm kiếm được hơn.

Answer 2

Thực ra tôi đã gặp phải vấn đề tương tự gần đây nhưng khác biệt duy nhất là có khoảng 300 điểm và tôi đã giải quyết nó bằng bitet (C++ STL). Đối với mỗi cặp điểm, nói (x [i], y [i]) và (x [j], y [j]), tôi đã tạo thành một bitet < 302> B [i] [j] và B [i] [j] [k] lưu trữ 1 nếu điểm thứ k nằm trên đoạn đường thẳng từ điểm i đến điểm j khác, tôi sẽ lưu trữ 0.

Bây giờ, theo cách sức mạnh vũ phu, tôi lấy ba điểm để tạo thành một hình tam giác, cho phép nói (x [i], y [i]), (x [j], y [j]) và (x [k], y [k]), sau đó một điểm, nói điểm thứ z, sẽ là bên trong tam giác nếu B [i] [j] [z] == B [i] [j] [k] & & B [j] [k] [z] == B [j] [k] [i] & & B [k] [i] [z] == B [k] [i] [j] vì một điểm bên trong tam giác sẽ hiển thị dấu hiệu tương tự một cạnh của tam giác là điểm tam giác thứ ba (không nằm ở bên này). Vì vậy, tôi nhận được ba biến bitet P = B [i] [j], Q = B [j] [k] và R = B [k] [i] và ở đó có bitwise AND sau đó áp dụng hàm count() để cung cấp cho tôi số bit hoạt động và do đó số lượng điểm trong tam giác. Nhưng hãy chắc chắn rằng bạn thay đổi biến P sao cho nó cho B [i] [j] [k] = 1 nếu không sau đó lấy bitwise không (~) của biến này.

Mặc dù giải pháp trên là vấn đề cụ thể, tôi hy vọng điều đó sẽ hữu ích. Đây là liên kết sự cố: http://usaco.org/current/index.php?page=viewproblem&cpid=660