VECTOR spoj – Tổng Vector

Nguồn đề bài: http://vn.spoj.com/problems/VECTOR/

1. Đề bài VECTOR spoj

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.

Input

Dòng thứ nhất ghi số 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).

Dòng cuối cùng ghi số hai số nguyên U V (|U|, |V| ≤ 109).

Output

Gồm một số duy nhất là số cách chọn thoả mãn.

Example

Input:
4
0 0
-1 2
2 5
3 3
2 5

Output:
4

2. Hướng dẫn VECTOR spoj

Nếu duyệt tổ hợp của N Vector thì độ phức tạp thuật toán là O(2^N), với n=30 thì không thể ăn hết điểm của bài này. Vì vậy cần giảm N xuống, thay bằng thuật toán duyệt phân tập (duyệt bằng cách chia đôi tập hợp – trong tập “Một số vấn đề trong tin học” hoặc KCBOOK) :

  • Chia tập hợp thành 2 tập con là A và B.
  • Duyệt tập A dùng mảng F[i,j] để đếm số cách chọn những vector từ A đề được tổng (i, j).
  • Duyệt tiếp tập B, với mỗi tổng (a, b) thu được, ta cộng vào biến Res (Result) theo công thức : Res := Res + f[u-a, v-b];
  • Biến res chính là kết quả bài toán.

3. Code tham khảo VECTOR spoj

* Admin đã bổ sung thêm code mẫu 27/06/2015 

a. Code pascal 1

b. Code pascal 2

Code của admin

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *