VMCXG - Cối xay gió

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho tập S gồm N điểm trên mặt phẳng thỏa mãn không có 3 điểm nào thẳng hàng. Cối xay gió là một quá trình bắt đầu với một đường thẳng d đi qua chỉ một điểm P thuộc S . Đường thẳng này quay theo ngược chiều kim đồng hồ xung quanh tâm P cho đến khi lần đầu tiên gặp một điểm khác nào đó của S . Điểm này, ký hiệu Q , lại được lấy làm tâm quay mới, và bây giờ đường thẳng d tiếp tục quay theo ngược chiều kim đồng hồ quanh tâm Q cho đến khi gặp điểm tiếp theo của S . Quá trình trên cứ tiếp tục như vậy.

Biết mỗi giây, đường thẳng d quay một góc 1 radian , hỏi sau khi quá trình được thực hiện T giây, đường thẳng d nhận mỗi điểm làm tâm quay trong bao nhiêu thời gian.

Input

  • Dòng đầu tiên ghi số nguyên N .
  • Dòng thứ i trong N dòng tiếp theo, mỗi dòng ghi 2 số nguyên x y là tọa độ của điểm thứ i thuộc tập S .
  • Dòng tiếp theo ghi số nguyên T .
  • Dòng cuối cùng ghi ba số nguyên a , b , c mô tả đường thẳng d có phương trình ax + by + c = 0 .
  • Dữ liệu trong input đảm bảo thỏa mãn các điều kiện của đề bài.

Output

  • Ghi ra N dòng. Dòng thứ i ghi một số thực w i thể hiện thời gian mà điểm i làm tâm quay.
  • Các số cần ghi ra với độ sai số không quá 10 -2

Giới hạn

  • Trong 40% test đầu tiên, N ≤ 50, T ≤ 100;
  • Trong 30% test tiếp theo, N ≤ 500, T ≤ 10 6 ;
  • Trong tất cả các test, N ≤ 5000, T ≤ 10 9 , a, b, c và các tọa độ có trị tuyệt đối không vượt quá 10 6 .

Chấm điểm

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Ví dụ 

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

Output:
0.000000
1.570796
0.785398
0.643806

  • Người up: voj
  • Nguồn bài: VM13 - Lê Ðôn Khuê