- محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی)
- محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی)
در این مسئله، $N$ پلیس وجود دارد که با $1$ تا $N$ شماره‌گذاری شده‌اند و $M$ دزد وجود دارد که با $1$ تا $M$ شماره‌گذاری شده‌اند. همه‌ی افراد (پلیس‌ها و دزدان) نقطه‌ای دوبعدی در یک صفحهٔ دکارتی هستند. مختصات پلیس $i$-ام را با $(Xp_i, Yp_i)$ و مختصات دزد $i$-ام را با $(Xt_i, Yt_i)$ نشان می‌دهیم.
یک دزد دستگیر می‌شود اگر مجموعه‌ای از پلیس‌ها وجود داشته باشد که یک چندضلعی محاط‌کننده بسازند به طوری که دزد اکیداً داخل (و نه روی) آن چندضلعی قرار بگیرد.
اداره‌ی پلیس می‌خواهد تعدادی (صفر یا بیشتر) پلیس به عنوان نیروی تقویتی اعزام کند تا مطمئن شود که همه‌ی دزدان دستگیر می‌شوند. مختصات این پلیس‌های اضافی به دلخواه انتخاب می‌شود (می‌توانند هر مقدار حقیقی‌ای داشته باشند)؛ اما اجازه‌ی جابه‌جایی پلیس‌هایی که در ابتدا حضور داشتند وجود ندارد. کمترین تعداد پلیس‌هایی که باید به عنوان نیروی تقویتی برای دستگیری همه‌ی دزدان اعزام شوند را محاسبه کنید.
ورودی
- اولین خط ورودی شامل یک عدد صحیح $T$ است که تعداد سناریوها را نشان می‌دهد. سپس توصیف $T$ سناریو در ادامه می‌آید.
- اولین خط هر مورد سناریو شامل دو عدد صحیح جدا شده با فاصله $N$ و $M$ است (اول $N$ می‌آید و سپس $M$).
- $N$ خط بعدی دنبال می‌شود. برای هر $i$ (1 ≤ $i$ ≤ $N$)، خط $i$-ام از این خطوط دو عدد صحیح جداشده با فاصله $Xp_i$ و $Yp_i$ را در خود دارد.
- $M$ خط دیگر دنبال می‌شود. برای هر $i$ (1 ≤ $i$ ≤ $M$)، خط $i$-ام از این خطوط دو عدد صحیح جداشده با فاصله $Xt_i$ و $Yt_i$ را در خود دارد.
خروجی
برای هر سناریو، یک خط شامل یک عدد صحیح چاپ کنید: حداقل تعداد افسران پلیس اضافی. (پاسخ می‌تواند صفر هم باشد.)
محدودیت‌ها
- $1 \le T \le 10$
- $0 \le N \le 10^5$
- $1 \le M \le 10^5$
- $|Xp_i|, |Yp_i| \le 2 \times 10^8$ برای هر $i$ معتبر
- $|Xt_i|, |Yt_i| \le 2 \times 10^8$ برای هر $i$ معتبر
- هیچ دو نفر (افسران پلیس یا دزدها) در یک موقعیت یکسان نیستند.
مثال
ورودی نمونه ۱
1
1 1
10 10
20 20
خروجی نمونه ۱
2
ارسال پاسخ برای این سؤال