[백준] 20648 - Rectangular Pasture (c++)

https://www.acmicpc.net/problem/20648

 

문제 요약

좌표평면에 있는 N마리의 소의 좌표가 주어진다. 

직사각형 모양의 울타리로 소를 가둘 계획이다. 울타리 하나로 가둘 수 있는 소의 집합의 개수를 구해라.

 

풀이 (N^2)

• 누적합
• 스위핑
• 좌표 압축

N이 충분히 작기 때문에 N^2 풀이를 생각할 수 있다.

두 소 i,j를 고정시키고 그 소를 포함하는 최소 넓이의 직사각형을 구한다. 그 직사각형을 위 아래로 확장시키는 경우의 수(직사각형 위에 점*직사각형 아래에 점)를 구한다. 각 x,y가 고유하기 때문에 이렇게 만든 직사각형에 포함되는 소의 집합 또한 고유하다. i<j인 (i,j) 쌍에 대해 모두 구해주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<int> xc,yc;
ll sum[3000][3000];

ll q(int sx,int sy,int ex,int ey) {
    return sum[ex][ey]-sum[ex][sy-1]-sum[sx-1][ey]+sum[sx-1][sy-1];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<array<int,2>> v(n);
    for(auto& [x,y]:v)cin>>x>>y,xc.push_back(x),yc.push_back(y);
    sort(xc.begin(),xc.end());sort(yc.begin(),yc.end());
    for(auto& [x,y]:v) {
        x=lower_bound(xc.begin(),xc.end(),x)-xc.begin()+1;
        y=lower_bound(yc.begin(),yc.end(),y)-yc.begin()+1;
        sum[x][y]++;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    ll ans=1+n;
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            auto [x1,y1]=v[i];
            auto [x2,y2]=v[j];
            if(y1>y2)
                swap(y1,y2);
            //cout<< q(x1,y2,x2,n)<< ' '<<q(x1,1,x2,y1)<<'\n';
            ans+=q(x1,y2,x2,n)*q(x1,0,x2,y1);    
        }
    }
    cout<<ans;
}