Submission #921292

#	Time	Username	Problem	Language	Result	Execution time	Memory
921292		AverageAmogusEnjoyer	Garden (JOI23_garden)	C++17	6 / 100	3038 ms	10164 KiB

garden

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
const int nax = 500500;
int n,m,d;
int pts[nax][2];
int pts2[nax][2];
int X1,Y1,X2,Y2;
bool chk(int x,int y) {
    return X1 <= x && x <= X2 && Y1 <= y && y <= Y2;
}
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    cin >> n >> m >> d;
    for (int i=0;i<n;i++) {
        cin >> pts[i][0] >> pts[i][1];
    }
    for (int i=0;i<m;i++) {
        cin >> pts2[i][0] >> pts2[i][1];
    }
    int ans = 1e9;
    for (X1=0;X1<=2*d;X1++) {
        for (Y1=0;Y1<=2*d;Y1++) {
            for (X2=X1;X2<=2*d;X2++) {
                for (Y2=Y1;Y2<=2*d;Y2++) {
                    int c1 = 0, c2 = 0;
                    for (int i=0;i<n;i++) {
                        bool G = chk(pts[i][0],pts[i][1]) |
                                 chk(pts[i][0]+d,pts[i][1]) | 
                                 chk(pts[i][0],pts[i][1]+d) | 
                                 chk(pts[i][0]+d,pts[i][1]+d);
                        c1 += G;
                    }
                    for (int i=0;i<m;i++) {
                        bool G = (X1 <= pts2[i][0] && pts2[i][0] <= X2) 
                               | (X1 <= pts2[i][0] + d && pts2[i][0] + d <= X2) 
                               | (Y1 <= pts2[i][1] && pts2[i][1] <= Y2) 
                               | (Y1 <= pts2[i][1] + d && pts2[i][1] + d <= Y2);
                        c2 += G;
                    }
                    if (c1 == n && c2 == m) {
                        cmin(ans,(X2-X1+1)*(Y2-Y1+1));
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25