Description

เรื่องราวเริ่มต้นจากความเข้าใจผิดของ คัง โมยอน คุณหมอสาวคนสวยแห่งโรงพยาบาลแฮซอง ที่ได้มีโอกาสมารักษาหัวขโมยที่ขโมยโทรศัพท์มือถือของ

ซอ แดยอง เพื่อนทหารร่วมทีมเดียวกับ ยู ชีจิน กัปตันหนุ่ม จนทำให้ ยู ชีจิน (กัปตันยู) และ ซอ แดยอง เพื่อนหนุ่ม ที่ออกเวรมาพร้อมกัน ต้องมาช่วยกันตามหาโทรศัพท์มือถือที่หายไป

โดยกัปตันยูได้ตามสัญญาณโทรศัพท์มือถือของเพื่อนตน จากพิกัด GPS ในที่ถูกส่งมาในรูปแบบ (latitude, longitude​)

แต่กัปตันยูไม่มีเวลาพอที่จะคำนวณทิศทางและระยะทางด้วยตัวเอง กัปตันยูจึงต้องขอร้องน้องๆ ให้ช่วยเขียนระบบติดตามโทรศัพท์มือถือขอเพื่อนหนุ่ม เพื่อที่จะติดตามหัวขโมยไปได้ทันเวลา

โดยโปรแกรมจะต้องสามารถระบุทิศทาง 8 ทิศ ที่กัปตันยูต้องไป (N, NE, E, SE, S, SW, W, NW) พร้อมระยะทาง (กิโลเมตร)

สถานการณ์ตัวอย่าง

สมมติให้กัปตันยูเริ่มต้นติดตามจากพิกัด (8.661076, 99.926741)

โดย โทรศัพท์มือถือจะส่งพิกัดมาเป็น (8.641844, 99.897918) (8.539449, 99.940461) และ (8.493359, 99.730259) ตามลำดับ

ดังนั้น

พิกัด #1 (8.641844, 99.897918) จะห่างจากพิกัดเริ่มต้น (8.661076, 99.926741)​ เป็นระยะ 3.83 กิโลเมตร ไปยังทิศ SW

พิกัด #2 (8.539449, 99.940461) จะห่างจากพิกัด #1 (8.641844, 99.897918)​ เป็นระยะ 12.32 กิโลเมตร ไปยังทิศ SE

พิกัด #3 (8.493359, 99.730259) จะห่างจากพิกัด #2 (8.539449, 99.940461)​ เป็นระยะ 23.70 กิโลเมตร ไปยังทิศ SW

สูตรการหาระยะทางจากพิกัด 2 พิกัด

โดยที่

d คือระยะทางระหว่างพิกัด 2 พิกัด

r คือรัศมีของโลก (กำหนดให้รัศมีของโลกมีค่า 6378.137 กิโลเมตร)

φ1, φ2: latitude ของจุดที่ 1 และ latitude ของจุดที่ 2, (ในหน่วย radians)

λ1, λ2: longitude ของจุดที่ 1 และ longitude ของจุดที่ 2, (ในหน่วย radians)​

หากน้องๆสนใจรายละเอียดเพิ่มเติมสามารถศึกษาได้ที่ https://en.wikipedia.org/wiki/Haversine_formula​ (opens new window)

Hint

หน่วยของ (lat, long) มีหน่วยเป็น degree

Radians = Degrees * PI / 180 (กำหนดให้ PI = 3.1416)

Specification

Input Specification	Output Specification
มีทั้งหมด N+2 บรรทัด บรรทัดแรก: จำนวนเต็ม 1 <= N <= 10 เป็นจำนวนพิกัด (lat, long) ที่กัปตันยูได้รับ บรรทัดที่สอง: จำนวนจริง เป็นพิกัดเริ่มต้น (lat, long)​ N บรรทัดต่อมา: จำนวนจริง เป็นพิกัด (lat, long) ที่กัปตันยูได้รับ​ โดยรับประกันว่าขอบเขตของพิกัดทั้งหมดจะอยู่เหนือเส้นศูนย์สูตรและอยู่ในทวีปเอเชีย และพิกัดไม่ซ้ำตำแหน่งเดิมอย่างแน่นอน	มีทั้งหมด N บรรทัด​ แสดงระยะทาง (กิโลเมตร) เป็นทศนิยมสองตำแหน่ง พร้อมทิศทาง

Sample Case

Sample Input	Sample Output
3 (8.661076, 99.926741) (8.641844, 99.897918) (8.539449, 99.940461) (8.493359, 99.730259)	#1 Distance: 3.83km Direction: SW #2 Distance: 12.32km Direction: SE #3 Distance: 23.70km Direction: SW
4 (13.831635, 100.773530) (13.831635, 100.767919) (13.834010, 100.762083) (13.909046, 100.762083) (14.190914, 101.185168)	#1 Distance: 0.61km Direction: W #2 Distance: 0.68km Direction: NW #3 Distance: 8.35km Direction: N #4 Distance: 55.43km Direction: NE