Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Destruction là con tàu chiến mà Fuyu-san đã tự tay thiết kế - với con tàu này, chinh phục bất kỳ thế giới nào đối với Fuyu-san đều không phải là việc gì khó khăn cả.

Một lần, Fuyu-san lái tàu chiến của mình tiến công vào căn cứ của hành tinh E.

Để đơn giản, ta có thể tưởng tượng như sau: căn cứ này là một hình chữ nhật nằm trên hệ tọa độ Cartesian-2D, các cạnh song song với trục tọa độ, với điểm dưới trái là gốc tọa độ (0, 0) và điểm trên phải là (n, m). Căn cứ bao gồm k khu phức hợp, mỗi khu phức hợp được coi như một điểm nằm trong hình chữ nhật ở trên.

Fuyu-san muốn thử nghiệm thứ vũ khí mới của cô – một hệ thống oanh tạc quỹ đạo (orbital bombardment) gây sát thương trên một vùng hình vuông có tọa độ các đỉnh đều là các số nguyên, đồng thời cạnh tạo với trục tọa độ một góc 45 độ, đường chéo hình vuông có độ dài là a đơn vị (hiển nhiên a chẵn). Để tránh lãng phí hỏa lực, đồng thời giữ căn cứ lâu dài nhằm oanh tạc (heh, sở thích kỳ quặc của cô có vẻ không có điểm dừng?), Destruction sẽ chỉ được phép bắn phá một vùng hình vuông duy nhất, và vùng đó phải nằm trọn vẹn trong không gian căn cứ.

Đôi khi, những giới hạn lại là cơ sở cho những ý tưởng. Lần này cũng vậy. Fuyu-san tự hỏi, với chỉ một lần oanh tạc duy nhất, thì giá trị kỳ vọng của số lượng khu phức hợp bị oanh tạc sẽ là bao nhiêu.

Về khái niệm giá trị kỳ vọng trong lý thuyết xác suất, có thể tham khảo tại đây: https://en.wikipedia.org/wiki/Expected_value

Đương nhiên, một câu hỏi đơn giản như vậy, dù thú vị, nhưng không đủ để thách thức khả năng của cô nàng với cái tên đại diện cho tâm hồn đầy băng giá này. Và giờ, như một thói quen, cô thách đố thử thách này cho các bạn.

Bạn có sẵn sàng chấp nhận và vượt qua được thử thách của Fuyu-san?

Dòng đầu tiên chứa bốn số nguyên n, m, k, a (2 ≤ n, m ≤ 105; 0 ≤ k ≤ min((n + 1) * (m + 1), 106); 2 ≤ a ≤ min(n, m), a chẵn).

k dòng tiếp theo, mỗi dòng chứa 2 số nguyên xi, yi (0 ≤ xi ≤ n, 0 ≤ yi ≤ m); biểu diễn tọa độ của mỗi khu phức hợp. Input đảm bảo, không có 2 khu phức hợp nào có chung tọa độ.

In ra một số thực duy nhất, là giá trị kỳ vọng của số lượng khu phức hợp bị oanh tạc khi Fuyu-san tấn công một vùng hình vuông duy nhất có tọa độ các đỉnh đều là các số nguyên, đồng thời cạnh tạo với trục tọa độ một góc 45 độ và đường chéo có độ dài là a đơn vị. Đáp án được chấp nhận với sai số 10 - 6.

Bản đồ căn cứ và các vị trí có thể oanh tạc ở ví dụ trên có thể được biểu diễn như sau (tọa độ mục tiêu có màu tím):