Advertisement
tepyotin2

Square Overlap

Jul 7th, 2025
468
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. struct Square{
  8.     ll x1, y1;
  9.     ll x2, y2;
  10.     bool operator<(const Square &a) const{
  11.         return x1<a.x1;
  12.     }
  13. };
  14.  
  15. int n;
  16. ll k;
  17.  
  18. int main(){
  19.     freopen("squares.in", "r", stdin);
  20.     freopen("squares.out", "w", stdout);
  21.    
  22.     cin >> n >> k;
  23.     /*
  24.     Since the input are all the centers of squares and we know k is the size of the side lengths
  25.     of the squares, we can use the value k to get the corners of the squares which become x1, y1
  26.     x2, y2, and then we will use those values towards the calculation and finding the overlaps.
  27.     */
  28.     vector<Square> square;
  29.     for(int i=0; i<n; i++){
  30.         ll x, y;
  31.         cin >> x >> y;
  32.         ll half = k/2;
  33.         Square s;
  34.         s.x1 = x-half;
  35.         s.x2 = x+half;
  36.         s.y1 = y-half;
  37.         s.y2 = y+half;
  38.         square.push_back(s);
  39.     }
  40.     sort(square.begin(), square.end());
  41.     /*
  42.     After sorting from left to right based on the x values, we loop for each square, we find every
  43.     square before it and test a few conditions. First, we check if the x2 of the square we're comparing
  44.     the current square to is more than the x1 of the current square. If so, then the first condition is
  45.     valid and we can therefore find the area of overlap which is the minimum of the maximum of x values
  46.     minus the maximum of the minimum x values and it is the same thing when calculating for y overlap.
  47.     If the area of the calculation of overlap is greater than zero, it means that there is an overlap.
  48.     We don't stop yet and continue to check every square to see if there is another overlap, if there
  49.     is then we can print out -1 and must return 0 or else will continue to loop and eventually print
  50.     out the overlap. At the end, if there is one overlap, we print the area of the overlap.
  51.     */
  52.     vector<Square> active;
  53.     int overlaps = 0;
  54.     ll ans = 0;
  55.     for(int i=0; i<n; i++){
  56.         for(int j=0; j<i; j++){
  57.             if(square[j].x2<=square[j].x1) continue;
  58.             if(square[j].x2>square[i].x1){
  59.                 ll dx = min(square[j].x2, square[i].x2)-max(square[i].x1, square[j].x1);
  60.                 if(dx<0) dx = 0;
  61.                 ll dy = min(square[j].y2, square[i].y2)-max(square[j].y1, square[i].y1);
  62.                 if(dy<0) dy = 0;
  63.                 if(dx>0 && dy>0){
  64.                     overlaps++;
  65.                     ans = dx*dy;
  66.                     if(overlaps>1){
  67.                         cout << -1 << '\n';
  68.                         return 0; //!!missing return
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.     }
  74.     if(overlaps == 1){
  75.         cout << ans << '\n';
  76.     }else{
  77.         cout << 0 << '\n';
  78.     }
  79.    
  80.     return 0;
  81. }
  82.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement