Universal Cup Judging System

Universal Cup

Límite de tiempo: 4.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

لديك $N$ نقاط مختلفة في المستوى ثنائي الأبعاد، مرقمة من $1$ إلى $N$. إحداثيات النقطة $i$ هي $(x_i, y_i)$.

لكل نقطة لون. يوجد إجمالاً $N$ ألوان مرقمة من $1$ إلى $N$، ولون النقطة $i$ هو $c_i$.

مهمتك هي اختيار أربع نقاط ذات ألوان مختلفة مثنى مثنى، وتوصيلها بأي ترتيب لتكوين رباعي أضلاع. قد يحتوي رباعي الأضلاع على زاوية داخلية قياسها $180^\circ$ بالضبط، ولكن لا يجوز أن يتقاطع أي زوج من الأضلاع غير المتجاورة.

حدد ما إذا كان من الممكن تكوين رباعي أضلاع كهذا. إذا كان ذلك ممكناً، فليكن $S$ هو أكبر مساحة ممكنة عبر جميع رباعيات الأضلاع الصالحة، واطبع $2S$ كعدد صحيح. وإذا لم يكن ذلك ممكناً، فاطبع $0$.

يوجد $T$ حالات اختبار مستقلة.

الإدخال

يُعطى الإدخال بالصيغة التالية:

T
case1
case2
:
caseT

هنا، تُعطى كل حالة $\text{case}_i$ بالشكل التالي:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • جميع قيم الإدخال هي أعداد صحيحة.
  • $1 \le T \le 10^4$
  • $4 \le N \le 10^5$
  • $|x_i|, |y_i| \le 10^8$
  • $1 \le c_i \le N$
  • إذا كان $i \neq j$، فإن $(x_i, y_i) \neq (x_j, y_j)$.
  • مجموع $N$ الكلي عبر جميع حالات الاختبار لا يتجاوز $10^5$.

الإخراج

لكل حالة اختبار، اطبع الإجابة في سطر مستقل.

أمثلة

مثال الإدخال 1

4
6
2 4 1
5 4 2
6 2 3
5 1 1
2 1 2
1 3 4
4
1 1 1
3 5 2
7 2 3
4 3 4
5
0 0 1
0 1 2
1 0 2
0 2 3
2 0 3
4
0 0 1
0 100000000 2
100000000 0 3
100000000 100000000 4

مثال الإخراج 1

15
17
0
20000000000000000

ملاحظة

في المثال الأول، يؤدي توصيل النقاط $1, 2, 3, 6$ بهذا الترتيب إلى تكوين رباعي أضلاع صالح مساحته $15/2$، وهي المساحة القصوى بين جميع الخيارات الصالحة. رباعي الأضلاع المكوّن من النقاط $1, 2, 4, 5$ مساحته $9$، لكن النقطتين $1$ و $4$ لهما نفس اللون، لذا فهو غير صالح.

في المثال الثاني، يوجد رباعي أضلاع صالح، لكن لا يوجد أي رباعي أضلاع محدب يحقق المتطلبات.

في المثال الثالث، لا يمكن تكوين أي رباعي أضلاع صالح.

كما هو موضح في المثال الرابع، يمكن أن تكون الإجابة كبيرة جداً.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.