المسائل ذات المسائل الفرعية

في منصة Codeforces، تكون المسألة إما محلولة أو غير محلولة. أما في المنصّات الأخرى، فتُقسّم المسائل إلى مسائل فرعية (Subproblems) تختلف في القيود، ويُمنح المشارك نقاطًا بناءً على كل مسألة فرعية، بحيث يُظهر الحكم النهائي (verdict) الدرجة الإجمالية التي حصل عليها. هذا النمط شائع في المسابقات الكبرى مثل الأولمبيادات الوطنية والدولية.

Iso-celestial

Codeforces

يُعطى لك عدد من النقاط \(N\) على المستوى الإحداثي ثنائي الأبعاد، حيث \(N \leq 3000\). المطلوب هو حساب عدد المجموعات الثلاثية من النقاط التي تُشكّل مثلثًا متساوي الساقين.

نظام التقييم

تتكون المسألة من ثلاث مسائل فرعية تختلف فقط في القيود المفروضة على \(N\)، كما هو موضّح في الجدول التالي:

المسألة الفرعية	القيود	النقاط
1	\(N = 3\)	33
2	\(N \leq 100\)	33
3		34

Note

في المسألة الفرعية الثالثة لا توجد قيود إضافية، أي أن القيود الوحيدة المطبّقة هي تلك الواردة في نص المسألة الأصلي. بالنسبة إلى \(N\)، يعني ذلك أنّ \(1 \leq N \leq 3000\).

الحل للمسألة الفرعية 1

في هذه المسألة لدينا ثلاث نقاط فقط، وبالتالي إما أنّها تُشكّل مثلثًا متساوي الساقين أو لا. للتحقّق من ذلك، يمكننا فحص ما إذا كان هناك ضلعان متساويان في الطول:

#include"bits/stdc++.h"
using namespace std;

int n;

long long x[3001], y[3001];

long double dist(int i, int j) {
    long double dy = y[i] - y[j];
    long double dx = x[i] - x[j];

    return sqrtl(dy * dy + dx * dx);
}

bool f(int a, int b, int c) {
    long double ab = dist(a, b);
    long double ac = dist(a, c);
    long double bc = dist(b, c);

    return (ab == ac || ab == bc || ac == bc);
}

int main() {
    cin >> n;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i]>> y[i];
    }

    cout << f(0, 1, 2);
}

الحل للمسألة الفرعية 2

بما أن \(N \leq 100\) في هذه المسألة الفرعية، يمكننا المرور على جميع المجموعات الثلاثية واختبار كل واحدة منها باستخدام الحل من المسألة السابقة. هذه الطريقة تُجري عددًا من الفحوصات قدره \(O(N^3)\)، وهي بطيئة جدًا بالنسبة للمسألة الكاملة التي يكون فيها \(N \leq 3000\).

#include"bits/stdc++.h"
using namespace std;

int n;

long long x[3001], y[3001];

long double dist(int i, int j); // كما في السابق
bool f(int a, int b, int c); // كما في السابق

int main () {

    cin >> n;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i]>> y[i];
    }

    int counter = 0;

    for (int i = 0 ; i < n ; i++) {
        for (int j = i + 1 ; j < n ; j++) {
            for (int k = j + 1 ; k < n ; k++) {
                if (f(i, j, k)) counter++;
            }
        }
    }

    cout << counter;
}

الحل للمسألة الفرعية 3 (الحل الكامل)

في هذه المرحلة، نحتاج إلى التفكير بطريقة مختلفة واستخدام الملاحظات للوصول إلى حل أسرع. لنفترض وجود نقطة واحدة \(P\)، ونحسب المسافة بينها وبين كل نقطة أخرى.

يمكننا ملاحظة أنه إذا كانت هناك نقطتان \(X\) و\(Y\) على نفس المسافة من النقطة \(P\)، فإن المثلث \((P, X, Y)\) سيكون متساوي الساقين. وإذا وُجدت \(K\) نقاط جميعها على نفس المسافة من \(P\)، فإنّ أي زوج من هذه النقاط عند جمعه مع \(P\) يُشكّل مثلثًا متساوي الساقين.

من هذه الملاحظة، نحصل على خوارزمية تُجري \(O(N^2)\) عملية. لكل نقطة \(P\)، نمر على جميع النقاط الأخرى \(Q\) ونحصي عدد المرات التي تظهر فيها كل مسافة مميزة. بعد ذلك، نمر على جميع المسافات المميزة. ولنفرض أن عدد التكرارات لتلك المسافة هو \(C\)، فنضيف \(\displaystyle {C \choose 2}\) إلى الجواب.

#include"bits/stdc++.h"
using namespace std;

int n;

long long x[3001], y[3001];

long double dist (int i, int j); // كما في السابق

int main () {

    cin >> n;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i]>> y[i];
    }

    int counter = 0;

    for (int i = 0 ; i < n ; i++) {
        long double all[n];

        for (int j = 0 ; j < n ; j++) {
            all[j] = dist(i, j);
        }

        sort(all, all + n);

        int cnt = 1;

        for (int j = 1 ; j < n ; j++) {
            if (all[j] != all[j-1]) {
                counter += cnt * (cnt - 1) / 2;
                cnt = 0;
            }
            cnt++;
        }

        counter += cnt * (cnt - 1) / 2;
    }

    cout << counter;
}

يتم تنفيذ عملية المرور على المسافات المختلفة بترتيبها بعد الفرز، ثم المرور عليها بترتيب تصاعدي، ولكن مع اتخاذ إجراء فقط عند تغيّر المسافة الحالية عن السابقة. ولتبسيط الكود، نستفيد من حقيقة أن المسافة بين النقطة ونفسها ستكون عند الفهرس \(0\) في المصفوفة المرتّبة، مما يسمح لنا ببدء الحلقة من الفهرس \(1\).