Problem ID:
f_footer
Points:
2.8 (partial)
Time limit:
6.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem types
Ngày đầu năm mới, mẹ của
quyết định rằng cậu sẽ là người mang lại may mắn cho cả xóm. Bà gọi cậu dậy từ sớm, bảo cậu thay quần áo cho thật đẹp trai và dặn dò: ''Con phải đi xông đất từng nhà trong xóm để mang lại phúc lộc cho mọi người nhé!''Biết rằng, trong xóm của
có ~n~ nhà ~(2 \le n \le 1000)~. Khi chiếu lên mặt phẳng tọa độ ~Oxy~, mỗi ngôi nhà mang một tọa độ ~(x, y)~ riêng biệt.dù hơi ngái ngủ, nhưng vẫn vui vẻ nhận nhiệm vụ. Tuy nhiên cậu có kế hoạch riêng cho mình. Trước khi đi, cậu đã cẩn thận ghi lại danh sách gồm ~m~ nhà cậu sẽ xin lì xì trong hành trình của mình. Kết hợp sự lười biếng của mình cùng với kế hoạch săn lì xì, muốn tìm một đường thẳng sao cho khoảng cách từ tất cả các nhà trong xóm đến đường thẳng ấy là nhỏ nhất có thể, đồng thời đường thẳng ấy chia các nhà mà cậu dư định xin lì xì và các nhà còn lại thành hai miền riêng biệt.
Sau khi tính toán và xác định được đường thẳng ~ax + by + c = 0~, cậu vừa đi vừa ngâm nga vài câu thơ về Tết:
Sau hành trình đầy ắp lì xì ấy,
hứa sẽ lì xì cho bất kỳ ai tìm ra được hệ số ~a, b, c~ (chuẩn hóa ~a^2 + b^2 = 1~) mà cậu đã tính toán trước khi bắt đầu. Do có thể có nhiều bộ số ~a, b, c~ thỏa mãn, chấp nhận tất cả các bộ số thỏa mãn nếu sai số tổng khoảng cách không vượt quá ~10^{-5}~. Bạn hãy thử săn lì xì từ nhé!Dữ liệu
- Dòng đầu tiên chứa ~2~ số nguyên ~n, m~ ~(2 \le m \le n \le 1000)~
- ~m~ dòng tiếp theo chứa tọa độ nguyên của những nhà sắp được xin lì xì ~(-10^6 \le x, y \le 10^6)~.
- ~n - m~ dòng tiếp theo chứa tọa độ nguyên của những nhà không được xin lì xì.
Kết quả
- Một dòng duy nhất chứa ~3~ số thực ~a, b, c~ sau khi chuẩn hóa ~a^2 + b^2 = 1~. Dữ liệu đảm bảo luôn có một bộ số thỏa mãn.
Giới hạn
- Subtask ~1~ ~(20\%)~: các nhà ở mỗi phân loại được xếp thành đường thẳng, hai đường thẳng này song song.
- Subtask ~2~ ~(80\%)~: không có ràng buộc nào thêm.
Ví dụ 1
Dữ liệu
4 2
0 0
0 1
2 0
2 1
Kết quả
1 0 -1
Comments