//
// Created by adavy on 5/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, M, D;
struct Sieve{
set<int> vals;
// a circular set, from 0 to D, maintain the maximum gap in the sieve
set<int, greater<int>> gaps;
void insert(int x){
if (vals.find(x) != vals.end()) return;
if (vals.size() == 0){
vals.insert(x);
return;
}
// get index of left and right neighbours
auto right_it = vals.lower_bound(x);
if (right_it == vals.end()){
right_it = vals.begin();
}
int right_nei = *right_it;
auto left_it = right_it;
if (left_it == vals.begin()){
left_it = vals.end();
}
left_it--;
int left_nei = *left_it;
if (left_nei != right_nei){
gaps.erase(gaps.find((right_nei - left_nei + D)%D));
}
gaps.insert((x - left_nei + D)%D);
gaps.insert((right_nei - x + D)%D);
vals.insert(x);
}
int get_max_gap(){
if (gaps.size() <= 1) return D;
return *gaps.begin();
} // beware of off by one error
};
bool inrange(int L, int x, int R){
if (L <= R){
return (x >= L && x <= R);
} else {
return (x >= L || x <= R);
}
}
int main(){
cin >> N >> M >> D;
int mnans = D*D;
int mnans2 = D*D;
set<int> pxvals, pyvals;
vector<pair<int,int>> lines;
vector<vector<int>> index(D); // indexed by y value
for(int i=0;i<N;++i){
int x, y; cin >> x >> y;
pxvals.insert(x);
pyvals.insert(y);
}
for (int i=0;i<M;++i){
int x, y; cin >> x >> y;
index[y].push_back(x);
}
for(auto&a:index){
sort(a.begin(), a.end());
}
// some extra code to solve naively
for(int L=0;L<D;++L) for(int R=0;R<D;++R) for(int T=0;T<D;++T) for(int B = 0; B<D;++B){
bool good = 1;
for (auto&x:pxvals){
if (!inrange(L, x, R)){
good = 0;
}
}
for (auto&y:pyvals){
if (!inrange(B, y, T)){
good = 0;
}
}
for(int y=0;y<D;++y){
for(auto&x:index[y]){
if (!(inrange(L, x, R)||inrange(B, y, T))){
good = 0;
}
}
}
if (!good) continue;
mnans2 = min(mnans2, ((R-L+D)%D+1)*((T-B+D)%D+1));
}
/*
for(int L=0;L<D;++L){
vector<vector<int>> events(D); // representing position of R
for(int Y=0;Y<D;++Y){
if (index[Y].size() == 0) continue;
auto fval = lower_bound(index[Y].begin(), index[Y].end(), L);
if (fval == index[Y].begin()) fval = index[Y].end();
// subtract
fval--;
if (fval == index[Y].end()) continue;
int x = *fval;
events[x].push_back(Y);
}
// set up and mantain the sieve
Sieve sieve;
// add all the normal points
for (auto&y:pyvals){
sieve.insert(y);
}
for (int R=(L-1+D)%D;;--R, R+=D, R%=D){
// condition to break if a normal point is missed out w.r.t. x axis
if (R!=(L-1+D)%D){
// if (R+1)%D is in pxvals, break
if (binary_search(pxvals.begin(), pxvals.end(), (R+1)%D)){
break;
}
}
mnans = min(mnans, ((R-L+D)%D+1)*(D+1-sieve.get_max_gap()));
// add events
for(auto&y:events[R] ){
sieve.insert(y);
}
if (R==L) break;
}
}*/
cout << mnans2 << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |