VECTOR spoj – Tổng Vector

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

Email 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 *