الجسيمات مو
Problem
بعد الخوض في دراسة الفيزياء في الحجر الصحي ، اكتشفت الأبقار "جزيئات مو"
إنهم يجرون حاليًا تجارب على جزيئات N "mu" (1 & le؛ N & le؛ 10
5 ). يحتوي الجسيم i على "دوران" موصوف بواسطة عددين صحيحين x
i و y
i في النطاق & ناقص؛ 10
9 & hellip؛ 10
9 شاملة. في بعض الأحيان اثنان من "جزيئات mu" يتفاعل. يمكن أن يحدث هذا فقط للجسيمات ذات الدوران (x
i ، y
i ) و (x
j ، y
j ) التي تحتوي على x i & le؛ x j و y i & le؛ y j . في ظل هذه الظروف ، يختفي أحد هذه الجسيمات بالضبط (ولا يحدث شيء للآخر). يمكن أن يحدث تفاعل واحد على الأكثر في أي وقت.
تريد الأبقار معرفة الحد الأدنى لعدد "جزيئات mu" التي يمكن أن تبقى بعد سلسلة عشوائية من التفاعلات.
إدخال
يحتوي السطر الأول على عدد صحيح واحد N ، وهو العدد الأولي لـ "جزيئات mu". يحتوي كل سطر من سطور N التالية على عددين صحيحين مفصولين بمسافة يحددان دوران هذا الجسيم. جميع الدورات مختلفة.
بصمة
عدد صحيح واحد ، الحد الأدنى لعدد "جزيئات mu" التي يمكن أن تبقى بعد تسلسل عشوائي من التفاعلات.
أمثلة
| # |
إدخال |
الإخراج |
ملاحظة
|
<الجسم>
| 1 |
4
10
0 1
-1 0
0 -1
| 1 |
أحد تسلسلات التفاعل المحتملة:
يتفاعل الجسيمان 1 و 4 ، ويختفي الجسيم 1.
يتفاعل الجسيمان 2 و 4 ، ويختفي الجسيم 4.
يتفاعل الجسيمان 2 و 3 ، ويختفي الجسيم 3.
يبقى الجسيم 2 فقط.
|
| 2 |
3
0 0
1 1
-1 3
| 2 |
لا يمكن أن يتفاعل الجسيم 3 مع أي من الجسيمات الأخرى ، لذلك يجب أن يبقى. يجب أيضًا أن يبقى أحد الجسيمات 1 و 2.
|