https://vn.spoj.com/problems/VECTOR
https://oj.vnoi.info/problem/VECTOR
Trong mặt phẳng tọa độ có N véc tơ. Mỗi một véc tơ được cho bởi hai chỉ số x và y. Tổng của hai véc tơ (xi, yi) và (xj, yj) được định nghĩa là một véc tơ (xi + xj, yi + yj). Bài toán đặt ra là cần chọn một số véc tơ trong N véc tơ đã cho sao cho tổng của các vec tơ đó là véc tơ (U, V).
Yêu cầu: Đếm số cách chọn thoả mãn yêu cầu bài toán đặt ra ở trên.
N (0 ≤ N ≤ 30).N dòng tiếp theo, dòng thứ i ghi các số nguyên xi, yi lần lượt là hai chỉ số của véc tơ thứ i. (|xi|, |yi| ≤ 100).U V (|U|, |V| ≤ 10^9).Gồm một số duy nhất là số cách chọn thoả mãn.
Input
4
0 0
-1 2
2 5
3 3
2 5
Output
4
Chia tập vector ban đầu thành 2 tập con, mỗi tập N/2 (~15 vectors). Với mỗi tập, sinh tất cả các vector có thể hình thành, do đó mỗi tập có khoảng 2^15 = 32K cách chọn.
Dựa trên 2 tập đã sinh, gọi là A và B, duyệt theo tập A, với mỗi vector sinh được từ tập A, chặt nhị phân trên tập B để tìm số cách sinh được phần còn lại của vector.
Độ phức tạp O(2^15 * 15)