1023.html

ระบบรักษาความปลอดภัยในปัจจุบันถือเป็นเรื่องที่สำคัญอย่างยิ่ง โดยเฉพาะในช่วงที่มีการก่อการร้อยเกิดขึ้นอย่างต่อเนื่องในส่วนต่างๆของโลก  มาตรการหนึ่งที่สำคัญคือการตรวจอาวุธก่อนขึ้นเครื่องบินโดยใช้เครื่องเอกซเรย์เป็นตัวถ่ายภาพและใช้ซอฟต์แวร์ช่วยในการวิเคราะห์รูปถ่าย

ซอฟต์แวร์ที่ใช้ในการตรวจอาวุธในกระเป๋าใบหนึ่งนั้น ทำงานโดยตรวจสอบส่วนประกอบความเหมือนกันของภาพเอกซเรย์สิ่งของภายในกระเป๋าเปรียบเทียบกับภาพของอาวุธต้นฉบับที่มีอยู่แล้ว ก็จะสามารถบอกได้ว่าเป็นอาวุธชนิดใด อย่างไรก็ตามวัตถุอื่นๆที่อยู่ในกระเป๋าอาจบังอาวุธอยู่ทำให้ภาพจากเครื่องเอกซเรย์ผิดพลาดไปบ้าง ดังนั้นการตัดสินว่าสิ่งของที่อยู่ในกระเป๋าเป็นอาวุธหรือไม่นั้นจะต้องมีค่าความเหมือนมากกว่าค่าหนึ่งที่กำหนดไว้ เช่น ถ้าภายในกระเป๋ามีส่วนของภาพอาวุธอยู่มากกว่า 80% เมื่อเปรียบเทียบกับภาพอาวุธที่สมบูรณ์จากต้นฉบับจะถือว่าพบอาวุธในกระเป๋า เป็นต้น

<b>โจทย์</b>
จงเขียนโปรแกรมเพื่อรับข้อมูล 
1) ภาพอาวุธ 
2) ภาพเอกซเรย์ และ
3) เปอร์เซนต์ความเหมือนของภาพต้นฉบับของอาวุธเพื่อใช้ตัดสินว่าเป็นอาวุธหรือไม่ เพื่อตรวจหาตำแหน่งอาวุธในภาพเอกซเรย์ อย่างไรก็ตาม การตรวจหาอาวุธภาพถ่ายเอกซเรย์นี้ จะละเลยปัญหาของการ สเกล โดยภาพอาวุธที่ต้องการตรวจจะขนาดเท่ากับภาพอาวุธในเอกซเรย์ และยังละเลยปัญหา การหมุน ของอาวุธในภาพด้วย โปรแกรมที่ต้องการให้เขียนจึงไม่ต้องพิจารณาในเรื่องเหล่านี้

<b>ข้อมูลนำเข้า</b>
ข้อมูลนำเข้าแบ่งเป็นสามส่วนคือ 
1) ภาพอาวุธ 
2) ภาพเอกซเรย์ และ
3) เปอร์เซนต์ความเหมือนของภาพต้นฉบับของอาวุธเพื่อใช้ตัดสิน โดยแต่ละส่วนจะเรียงต่อเนื่องกันไปตามลำดับ

<b>ส่วนแรก</b>ภาพอาวุธ บรรทัดแรกเป็นขนาดของภาพอาวุธ เป็นจำนวนเต็มบวกสองค่า w และ h เว้นวรรคด้วยช่องว่างหนึ่งช่อง จากนั้น h บรรทัดแต่ละบรรทัดจะประกอบด้วยสายอักขระยาว w โดยสายอักขระจะประกอบด้วย  ‘.’ และ ‘O’ โดย ‘.’ แทนที่ว่างซึ่งไม่ใช่ส่วนของอาวุธ และ ‘O’ เป็นส่วนของอาวุธ
<b>ส่วนที่สอง</b>ภาพเอกซเรย์ บรรทัดแรกเป็นขนาดของภาพเอกซเรย์ เป็นจำนวนเต็มบวกสองค่า x และ y (1 <= w <= x <= 50, 1 <= h <= y <= 50) เว้นวรรคด้วยช่องว่างหนึ่งช่อง จากนั้น y บรรทัดแต่ละบรรทัดจะประกอบด้วยสายอักขระยาว x โดยสายอักขระจะประกอบด้วย ตัวอักษร ‘A’-‘Z’ เท่านั้น
<b>ส่วนที่สาม</b>เปอร์เซนต์ความเหมือนที่ยอมรับได้ มีบรรทัดเดียวเป็นจำนวนเต็มบวก k (1 <= k <= 100)

<b>ข้อมูลส่งออก</b>
<b>บรรทัดแรก</b> แสดงจำนวนเต็มบวกสองตัวแสดงตำแหน่งบนภาพเอกซเรย์ของมุมบนซ้ายของภาพอาวุธ โดยคำนวณดังนี้

ค่าเปอร์เซนต์ความเหมือน = (จำนวน ‘O’ ที่ปรากฎในกระเป๋าและตำแหน่งตรงกับภาพอาวุธ) / (จำนวน ‘O’ ทั้งหมดในภาพอาวุธ (ไม่นับ ‘.’))

<b>จากตัวอย่าง  </b>สามารถคำนวณค่าเปอร์เซนต์ความเหมือนได้เท่ากับ 14/15 = 93.33%

แต่ถ้าหากว่าไม่พบอาวุธในภาพเอกซเรย์ ให้ส่ง "0 0" เป็นข้อมูลส่งออก โดยไม่ต้องมีเครื่องหมาย ""

<b>ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2548</b>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>7 5
<br />..OO...
<br />.OOOOOO
<br />.OO.O..
<br />..OO...
<br />..OO...
<br />10 10
<br />ABCDEFGHIJ
<br />KLMNOPQRST
<br />UVWOXYZOOO
<br />AAAAAAAAAA
<br />AAAAOBCDED
<br />AAAOOOOOOO
<br />AAAOOOOABC
<br />AAAAOOPQRO
<br />AAAAOOXXXO
<br />AAAAAAAAAA
<br />90</td>
				<td>5 3</td>
			</tr></table>