การจัดพิมพ์แผนที่ไม่ใช่งานง่าย ก่อนอื่นคุณต้องมีการแปลงที่เหมาะสมเพื่อแสดงรูปทรงกลมของโลกบนระนาบสองมิติ จากนั้นก็เกิดปัญหาอีกอย่าง นั่นคือแผนที่คุณภาพสูงส่วนใหญ่ใหญ่เกินกว่าจะพิมพ์ลงบนกระดาษแผ่นเดียว เพื่อแก้ปัญหานี้ ผู้จัดพิมพ์มักแบ่งแผนที่เป็นแผ่นสี่เหลี่ยมผืนผ้าหลายแผ่น และพิมพ์แต่ละแผ่นลงบนหนึ่งหน้า ในโจทย์นี้ คุณจะศึกษากระบวนการ “แบ่งเป็นแผ่น” นี้

International Cartographic Publishing Company (ICPC) ต้องการลดต้นทุนการพิมพ์ โดยทำให้จำนวนแผ่นที่ใช้สำหรับแผนที่น้อยที่สุด แม้ว่าขนาดของแผ่น (ซึ่งกำหนดโดยขนาดกระดาษ) และมาตราส่วนแผนที่จะคงที่ คุณก็ยังปรับปรุงผลได้ด้วยการปรับตำแหน่งตารางแผ่นแผนที่

ด้านซ้ายของรูป G.1 แสดงแผ่นแผนที่ 14 แผ่นที่ปกคลุมบริเวณหนึ่ง ด้านขวาแสดงวิธีปกคลุมบริเวณเดียวกันด้วยเพียง 10 แผ่น โดยไม่เปลี่ยนขนาดหรือทิศทางของแผ่น

รูป G.1: วิธีแบ่ง Texas เป็นแผ่นแผนที่สองแบบที่เป็นไปได้

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

สังเกตว่าแผ่นต้องเป็นส่วนหนึ่งของตารางสี่เหลี่ยมผืนผ้าที่ขนานกับแกน $x$ และแกน $y$ กล่าวคือ แผ่นจะสัมผัสกันได้ตลอดทั้งด้านเท่านั้น และไม่สามารถหมุนได้ อีกทั้งแม้พิกัดนำเข้าทั้งหมดเป็นจำนวนเต็ม ตำแหน่งของแผ่นก็อาจมีพิกัดที่ไม่เป็นจำนวนเต็มได้

รูปหลายเหลี่ยมอาจสัมผัสเส้นขอบด้านนอกได้ (ดังในข้อมูลนำเข้าตัวอย่าง 2) อย่างไรก็ตาม เพื่อหลีกเลี่ยงปัญหาเลขทศนิยมลอยตัว คุณสามารถสมมติว่าคำตอบที่ดีที่สุดจะไม่เปลี่ยน แม้อนุญาตให้รูปหลายเหลี่ยมยื่นออกนอกแผ่นแผนที่เป็นระยะ $10^{-6}$

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีกรณีทดสอบเดียว บรรทัดแรกมีจำนวนเต็มสามตัว $n$, $x_s$ และ $y_s$ จำนวนจุดยอดของรูปหลายเหลี่ยมคือ $n$ ($3\le n\le 50$) และ $x_s$ กับ $y_s$ ($1\le x_s,y_s\le 100$) เป็นขนาดของแต่ละแผ่น แต่ละบรรทัดใน $n$ บรรทัดถัดมามีจำนวนเต็มสองตัว $x$ และ $y$ ($0\le x\le 10x_s$, $0\le y\le 10y_s$) ระบุจุดยอดของรูปหลายเหลี่ยมที่แทนบริเวณนั้น ตามลำดับตามเข็มนาฬิกาหรือทวนเข็มนาฬิกา

ข้อมูลส่งออก

แสดงจำนวนแผ่นน้อยที่สุดที่จำเป็นเพื่อปกคลุมพื้นที่ภายในทั้งหมดของรูปหลายเหลี่ยม

ตัวอย่าง

ข้อมูลนำเข้า 1

12 9 9
1 8
1 16
6 16
9 29
19 31
23 24
30 23
29 18
20 12
22 8
14 0
14 8

ข้อมูลส่งออก 1

10

ข้อมูลนำเข้า 2

4 5 7
10 10
15 10
15 17
10 17

ข้อมูลส่งออก 2

1