Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement