[LeetCode] 3623. Count Number of Trapezoids I

https://leetcode.com/problems/count-number-of-trapezoids-i/description/?envType=daily-question&envId=2025-12-02

LeetCode - Count Number of Trapezoids I

문제 유형: 기하학

문제 난이도: Medium

 

문제

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

A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.

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

Since the answer may be very large, return it modulo 10^9 + 7.

 

points[i] = [xi, yi] 로 점의 좌표 배열이 주어집니다.

네 점을 골라 만들 수 있는 사다리꼴의 개수를 구하시오.

밑변이 y축에 대해 수직이어야 합니다.

 

값이 너무 클 수 있으니, 1e9+7로 나눈 나머지를 구하시오.

 

풀이

서로다른 두 y레벨에서 각각 2개의 점을 골라서 밑변을 만들고, 그 두 밑변이 평행하면 사다리꼴이 만들어진다.

우선, 같은 y를 가진 점들의 수를 저장한다.

 

그 뒤, 같은 y들마다 만들 수 있는 밑변의 수를 계산한다.

이후, 이전 y레벨들의 모든 밑변과 현재 밑변 개수를 곱해서 사다리꼴의 개수를 누적한다.

 

코드

C++

class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        unordered_map<int, int> pointNum;
        const int MOD = 1e9 + 7;
        long long ans = 0, sum = 0;
        for(auto &point : points) {
            pointNum[point[1]]++;
        }
        for(auto& [_, pNum] : pointNum) {
            long long edge = (long long)pNum * (pNum - 1) / 2;
            ans += edge * sum;
            sum += edge;
        }
        return ans % MOD;
    }
};