Square Overlap

tepyotin2

Jul 7th, 2025

468

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.42 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Square{
ll x1, y1;
ll x2, y2;
bool operator<(const Square &a) const{
return x1<a.x1;
}
};
int n;
ll k;
int main(){
freopen("squares.in", "r", stdin);
freopen("squares.out", "w", stdout);
cin >> n >> k;
/*
Since the input are all the centers of squares and we know k is the size of the side lengths
of the squares, we can use the value k to get the corners of the squares which become x1, y1
x2, y2, and then we will use those values towards the calculation and finding the overlaps.
*/
vector<Square> square;
for(int i=0; i<n; i++){
ll x, y;
cin >> x >> y;
ll half = k/2;
Square s;
s.x1 = x-half;
s.x2 = x+half;
s.y1 = y-half;
s.y2 = y+half;
square.push_back(s);
}
sort(square.begin(), square.end());
/*
After sorting from left to right based on the x values, we loop for each square, we find every
square before it and test a few conditions. First, we check if the x2 of the square we're comparing
the current square to is more than the x1 of the current square. If so, then the first condition is
valid and we can therefore find the area of overlap which is the minimum of the maximum of x values
minus the maximum of the minimum x values and it is the same thing when calculating for y overlap.
If the area of the calculation of overlap is greater than zero, it means that there is an overlap.
We don't stop yet and continue to check every square to see if there is another overlap, if there
is then we can print out -1 and must return 0 or else will continue to loop and eventually print
out the overlap. At the end, if there is one overlap, we print the area of the overlap.
*/
vector<Square> active;
int overlaps = 0;
ll ans = 0;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
if(square[j].x2<=square[j].x1) continue;
if(square[j].x2>square[i].x1){
ll dx = min(square[j].x2, square[i].x2)-max(square[i].x1, square[j].x1);
if(dx<0) dx = 0;
ll dy = min(square[j].y2, square[i].y2)-max(square[j].y1, square[i].y1);
if(dy<0) dy = 0;
if(dx>0 && dy>0){
overlaps++;
ans = dx*dy;
if(overlaps>1){
cout << -1 << '\n';
return 0; //!!missing return
}
}
}
}
}
if(overlaps == 1){
cout << ans << '\n';
}else{
cout << 0 << '\n';
}
return 0;
}

Add Comment

Please, Sign In to add comment