- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
محمدمهدی و روزبه برای گشت‌و‌گذار به صفرقند رفته اند. صفرقند شهری عجیب و مالیاتی عجیب دارد! در حین گشت و گذار ناگهان محمدمهدی روزبه را گم می‌کند! او می‌داند که صفرقند یک صفحه‌ی مختصات دکارتی است و او در در مختصات $(x_m, y_m)$ قرار دارد. همچنین متوجه می‌شود که روزبه در مختصات $(x_r, y_r)$ است. اما دیدار دوباره‌ی روزبه به این سادگی نیست! :(
صفرقند دارای تعدادی ناحیه است، هر ناحیه یک مستطیل که اضلاع آن با محور $x$ها و $y$ها موازی است. عبور از مرز هر ناحیه یک تومان مالیات دارد.
همچنین می‌دانیم به ازای هر دو ناحیه از صفرقند، این دو ناحیه یا اشتراکی ندارند یا یکی زیرناحیه‌ی دیگری است.
حال محمد مهدی می‌خواهد بداند حداقل باید چقدر مالیات بدهد تا به روزبه برسد. به او کمک کنید...
ورودی
در سطر اول ورودی $x_m, y_m$ که مختصات محمدمهدی است آمده است. $(-10^9 \leq x_m, y_m \leq 10^9)$
در سطر دوم ورودی $x_r, y_r$ که مختصات روزبه است آمده است. $(-10^9 \leq x_r, y_r \leq 10^9)$
در سطر سوم ورودی عدد $n$ تعداد ناحیه‌های صفرقند آمده‌است. $(0 \leq n \leq 3\times10^4)$
در $n$ سطر بعد، در سطر $i$ام، ۴ عدد $x_1, y_1, x_2, y_2$ که مختصات نقطه‌ی پایین-چپ و بالا-راست ناحیه‌است. $(-10^9 \leq x_1 < x_2 \leq 10^9 , -10^9 \leq y_1 < y_2 \leq 10^9)$
تضمین می‌شود که محمد مهدی و روزبه روی مرز‌های ناحیه‌ها نیستند.
دقت کنید قرار گرفتن روی مرز نواحی هزینه‌ای ندارد بلکه تنها عبور از ناحیه برای ورود/خروج به آن ناحیه مالیات دارد.
خروجی
در تنها سطر خروجی میزان پولی که باید محمدمهدی خرج کند را چاپ کنید.
مثال
ورودی نمونه ۱
0 0
2 2
1
-1 -1 1 1
خروجی نمونه ۱
1
ورودی نمونه ۲
1 1
7 1
6
0 0 2 2
0 0 3 3
0 0 5 5
0 0 6 6
-10 -10 10 10
100 100 200 200
خروجی نمونه ۲
4
توضیحات
اگر یک مرز، مرز مشترک $m$ ناحیه باشد. عبور از آن $m$ تومان مالیت دارد.
در مثال اول، محمد مهدی در تنها ناحیه‌ی صفرقند قرار دارد و برای دیدن روزبه مجبور است از ناحیه خارج شود پس باید لاآقل ۱ تومان خرج کند.
در مثال دوم، محمد مهدی باید از مرز ۴ ناحیه‌ی نخست صفرقند عبور کند تا به روزبه برسد، پس باید لاآقل ۴ تومان خرج کند.
ارسال پاسخ برای این سؤال