راحتی برای گاوها
Problem
مرتع کشاورز جان را می توان به عنوان یک شبکه دو بعدی بزرگ از سلول ها (صفحه شطرنج بزرگ) نشان داد. در ابتدا مرتع خالی است.
کشاورز جان N (1≤N≤10
5) گاو را یکی یکی به مرتع اضافه می کند. گاو i یک سلول (x
i,y
i) را اشغال می کند که با سلول های دیگر گاوها متفاوت است (0≤x
i، yi≤1000).
اگر گاو دقیقاً سه گاو دیگر به صورت افقی و عمودی داشته باشد، «راحت» گفته می شود. کشاورز جان می خواهد شمارش کند که چند گاو در چراگاه او راحت هستند. برای هر i در فاصله 1…N، تعداد کل گاوهایی را که پس از افزودن گاو i به مرتع راحت هستند چاپ کنید.
ورودی:
خط اول شامل یک عدد صحیح N است. هر یک از N خطوط زیر شامل دو عدد صحیح جدا شده با فاصله است که مختصات (x,y) سلول گاو را نشان می دهد. تضمین شده است که همه سلول ها متفاوت هستند.
خروجی:
خط i-ام خروجی باید شامل تعداد کل گاوهایی باشد که پس از افزودن گاو i-امین به مرتع راحت هستند.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
توضیح |
<بدن>
| 1 |
8
0 1
10
1 1
1 2
2 1
2 2
3 1
3 2 |
0
0
0
1
0
0
1
2 |
پس از اضافه شدن 4 گاو اول، گاو در سلول (1،1) راحت است.
پس از افزودن 7 گاو اول، گاو در سلول (2،1) راحت است.
پس از افزودن 8 گاو اول، گاو در سلول های (2،1) و (2،2) راحت است. |