square-pasture

Square Pasture

لدى المزارع جون مرعيان مستطيلان. يريد أن يستبدلهما بـ مرعى مربع واحد يغطي كليهما. يجب أن تكون أضلاع المربع موازية للمحورين \(x\) و \(y\).

أوجد أصغر مساحة لمثل هذا المربع.

الإدخال (الملف square.in):

السطر الأول: أربعة أعداد صحيحة \(x_1, y_1, x_2, y_2\) — الركن السفلي الأيسر \((x_1, y_1)\) والركن العلوي الأيمن \((x_2, y_2)\) للمرعى الأول.
السطر الثاني: أربعة أعداد صحيحة بالصيغة نفسها للمرعى الثاني.

كل الإحداثيات بين \(0\) و \(10\)، مع \(x_2 > x_1\) و \(y_2 > y_1\). المرعيان لا يتداخلان ولا يتلامسان.

المخرجات (الملف square.out):

عدد صحيح واحد — أصغر مساحة للمربع.

مثال:

الإدخال:

6 6 8 8
1 8 4 9

المخرجات:

(المربع الذي ركناه \((1, 6)\) و \((8, 13)\) يغطي المرعيين.)

الحل

أولًا نجد أصغر مستطيل يغطي المرعيين. ضلعه الأيسر هو الأصغر من الضلعين الأيسرين، وضلعه الأيمن هو الأكبر من الضلعين الأيمنين، والأمر نفسه للضلعين السفلي والعلوي.

يغطي المربع المرعيين تمامًا عندما يغطي هذا المستطيل. لذلك يجب ألا يقل ضلع المربع عن عرض المستطيل ولا عن ارتفاعه، ويكفي مربع ضلعه \(\max(\text{width}, \text{height})\). الجواب هو مربع هذا الضلع.

تقرأ مسائل USACO الإدخال من ملف وتكتب المخرجات في ملف. الدالة freopen تربط cin و cout بهذين الملفين.

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

struct Point {
    int x;
    int y;
};

struct Rectangle {
    Point bottom_left;
    Point top_right;
};

int main() {
    freopen("square.in", "r", stdin);
    freopen("square.out", "w", stdout);

    Rectangle a, b;
    cin >> a.bottom_left.x >> a.bottom_left.y >> a.top_right.x >> a.top_right.y;
    cin >> b.bottom_left.x >> b.bottom_left.y >> b.top_right.x >> b.top_right.y;

    // the smallest rectangle that contains both rectangles
    int left = min(a.bottom_left.x, b.bottom_left.x);
    int bottom = min(a.bottom_left.y, b.bottom_left.y);
    int right = max(a.top_right.x, b.top_right.x);
    int top = max(a.top_right.y, b.top_right.y);

    int side = max(right - left, top - bottom);
    cout << side * side << "\n";
}