Educational Codeforces Round 68 (Rated for Div. 2) E. Count The Rectangles

E. Count The Rectangles

https://codeforces.com/contest/1194/problem/E

가로선과 세로선이 합쳐서 n개 주어진다.

가로선 2개와 세로선 2개를 선택해서 사각형을 만들 수 있는데, 이때 만들어지는 사각형의 개수를 구해보자.

가로선과 세로선을 입력받는데, 가로선은 y의 위치와 x1, x2의 위치, 세로선은 x의 위치와 y1, y2의 위치를 저장해놓자.

더 적은 선을 기준으로 탐색을 시작할 것이다. 이를 가로선이라고 해보자.

가로선을 기준으로 세로선들을 모두 비교할건데 기준이 되는 가로선을 세로선이 지나가는지 확인한다.

그리고 각 세로선들을 입력받은 순서대로 번호를 메긴 후에, 기준이 되는 가로선을 지나가는지 여부를 기록할 것이다.

이것을 비트셋 자료구조를 이용해서 저장한다. 최대 5000개이므로, 5000개의 비트를 할당하자.

그 다음에는 모든 가로선들에 대해 2개씩 묶어 공통의 세로선을 지니고 있는지 비교를 한다. 즉 교집합 연산을 한다.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { while (b) { a %= b, swap(a, b); }    return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
#define MAXN 100050
#define PI 3.14159265358979323846
#define MOD 1000000007
 
ll n, m, k;
ll a, b, c, d;
vector<pair<int, pii>> row, col;
vector<bitset<5005>> bs;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) col.push_back({ x1, {min(y1, y2), max(y1, y2)} });
        else row.push_back({ y1, {min(x1, x2), max(x1, x2)} });
    }
 
    if (row.size() > col.size()) swap(row, col);
    int rn = row.size(), cn = col.size();
    
    for (int i = 0; i < rn; i++) {
        bs.push_back(0);
        for (int j = 0; j < cn; j++) {
            if (row[i].second.first <= col[j].first && col[j].first <= row[i].second.second &&
                col[j].second.first <= row[i].first && row[i].first <= col[j].second.second) {
                bs[i].set(j);
            }
        }
    }
 
    ll cnt = 0;
    for (int i = 0; i < rn - 1; i++) {
        for (int j = i + 1; j < rn; j++) {
            ll temp = (bs[i] & bs[j]).count();
            cnt += ((temp - 1) * temp) / 2;
        }
    }
 
    cout << cnt;
    return 0;
}