[LeetCode] 3625. Count Number of Trapezoids II

https://leetcode.com/problems/count-number-of-trapezoids-ii/editorial/?envType=daily-question&envId=2025-12-03

LeetCode - Count Number of Trapezoids II

문제 유형: 기하학, 해시

문제 난이도: Hard

 

문제

You are given a 2D integer array points where points[i] = [xi, yi] represents the coordinates of the ith point on the Cartesian plane.

Return the number of unique trapezoids that can be formed by choosing any four distinct points from points.

A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.

 

points[i] = [xi, yi]로 구성된 점 배열 points가 주어진다.

네 점을 선택에서 만들어질 수 있는 사다리꼴의 개수를 구하시오.

 

풀이

기울기만으로는 두 선분이 평행하기만 한지, 같은 직선 위에 있는지 알 수 없다.

대신, 절편과 같은 직선의 상수값을 더하면 어느 정도 파악할 수 있다.

직선의 방정식 ax + by + c = 0에서, 두 점의 좌표를 이용해서, c = dy * x1 - dx * y1으로 식을 정리할 수 있다.

 

이제, 기울기 + c값의 조합으로 해당 직선 위에 선분 조합이 몇 개 나오는지를 구할 수 있다.

이 선분조합들의 곱을 누적하면 된다.

그러나, 이렇게 구해서 같은 기울기의 서로 다른 조합들간의 곱을 누적하면, 평행사변형의 경우, 두 번 중복카운트된다.

왜냐하면, 평행하는 변의 쌍이 두 개이기 때문이다.

 

그래서, 평행사변형의 성질을 이용해서, 같은 중점을 가지는 서로 다른 slope를 가지는 선분 쌍의 조합들만을 또 구해서, 그들의 곱 조합을 누적한 값을 빼주면 된다.

 

이러한 선분의 개수들은 모든 서로 다른 두 점 조합을 정규화해서 해싱하면 된다.

정규화는, 분수 꼴에서 최대공약수를 구해서 각각 나눈 뒤, 분모 부분의 음수를 제거(분자, 분모에 모두 -1 곱하기) 하면 된다.

 

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
using ll = long long;

struct PairHash {
    template <class T1, class T2>
    size_t operator () (pair<T1, T2> const &v) const {
        auto h1 = hash<T1>{}(v.first);
        auto h2 = hash<T2>{}(v.second);
        return h1 ^ h2;
    }
};

class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        int n = points.size();
        unordered_map<pair<ll, ll>, unordered_map<ll, int>, PairHash> slopeToIntercept;
        unordered_map<pair<ll, ll>, unordered_map<pair<ll, ll>, int, PairHash>, PairHash> midToSlope;

        for(int i = 0; i < n; i++) {
            ll x1 = points[i][0];
            ll y1 = points[i][1];
            for(int j = i + 1; j < n; j++) {
                ll x2 = points[j][0];
                ll y2 = points[j][1];
                ll dx = x1 - x2;
                ll dy = y1 - y2;

                ll g = std::gcd(dx, dy);
                dx /= g;
                dy /= g;
                if (dx < 0 || (dx == 0 && dy < 0)) {
                    dx = -dx;
                    dy = -dy;
                }

                pair<ll, ll> slope = {dy, dx};
                
                // line constant
                ll c = dy * x1 - dx * y1;
                pair<ll, ll> mid = {x1+x2, y1+y2};
                slopeToIntercept[slope][c]++;
                midToSlope[mid][slope]++;
            }
        }

        int ans = 0;
        for(auto &it : slopeToIntercept) {
            auto &inner = it.second;
            ll sum = 0;
            for(auto &kv : inner) {
                ll cnt = kv.second;
                ans += sum * cnt;
                sum += cnt;
            }
        }

        for(auto &it : midToSlope) {
            auto &inner = it.second;
            ll sum = 0;
            for(auto &kv : inner) {
                ll cnt = kv.second;
                ans -= sum * cnt;
                sum += cnt;
            }
        }

        return ans;
    }
};