Tap here to switch tabs
Problem
Submissions

Problem: Find the Number of Ways to Place People II

Find the Number of Ways to Place People II asks you to count ordered pairs where Alice is upper left of Bob and their axis-aligned rectangle contains no other person, including on its boundary.

Statement

You are given a two dimensional array points of size n, where points[i] = [x_i, y_i] represents the coordinates of the ithi^{ {th}} person on a Cartesian plane.

You need to select a pair of distinct people, placing Alice at point A=(xA,yA)A = (x_A, y_A) and Bob at point B=(xB,yB)B = (x_B, y_B), such that:

  • Alice is at the upper left position relative to Bob, meaning xA≤xBx_A \leq x_B and yA≥yBy_A \geq y_B.

  • No other person is located strictly inside or on the boundary of the rectangular region defined by Alice and Bob as opposite corners. Specifically, there is no third person at point C=(xC,yC)C = (x_C, y_C) such that xA≤xC≤xBx_A \leq x_C \leq x_B and yB≤yC≤yAy_B \leq y_C \leq y_A.

Return the total number of valid pairs of people (A,B)(A, B) that can be chosen.

Note: The rectangular region may have an area of 00, which occurs when xA=xBx_A = x_B or yA=yBy_A = y_B.

Constraints:

  • 2≤2 \leq n ≤1000\leq 1000, where n is the length of points

  • points[i].length =2= 2

  • −109≤-10^9 \leq points[i][0], points[i][1] ≤109\leq 10^9

  • All points[i] are distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find the Number of Ways to Place People II

Find the Number of Ways to Place People II asks you to count ordered pairs where Alice is upper left of Bob and their axis-aligned rectangle contains no other person, including on its boundary.

Statement

You are given a two dimensional array points of size n, where points[i] = [x_i, y_i] represents the coordinates of the ithi^{ {th}} person on a Cartesian plane.

You need to select a pair of distinct people, placing Alice at point A=(xA,yA)A = (x_A, y_A) and Bob at point B=(xB,yB)B = (x_B, y_B), such that:

  • Alice is at the upper left position relative to Bob, meaning xA≤xBx_A \leq x_B and yA≥yBy_A \geq y_B.

  • No other person is located strictly inside or on the boundary of the rectangular region defined by Alice and Bob as opposite corners. Specifically, there is no third person at point C=(xC,yC)C = (x_C, y_C) such that xA≤xC≤xBx_A \leq x_C \leq x_B and yB≤yC≤yAy_B \leq y_C \leq y_A.

Return the total number of valid pairs of people (A,B)(A, B) that can be chosen.

Note: The rectangular region may have an area of 00, which occurs when xA=xBx_A = x_B or yA=yBy_A = y_B.

Constraints:

  • 2≤2 \leq n ≤1000\leq 1000, where n is the length of points

  • points[i].length =2= 2

  • −109≤-10^9 \leq points[i][0], points[i][1] ≤109\leq 10^9

  • All points[i] are distinct.