3025. 人員站位的方案數 I

• 輸入：
  2 <= n <= 50
  points[i].length == 2
  0 <= points[i][0], points[i][1] <= 50
  points[i] 點對兩兩不同。

// 按x降序，按y升序
int cmp(const void *a, const void *b) {int *p = *(int **)a;int *q = *(int **)b;if(p[0] == q[0]){return p[1]-q[1];} else return q[0]-p[0];
}
// 判斷c點是否在a為右下角，b為左上角的矩形和邊界內
bool IsPad(int *pointa, int *pointb, int *pointc) {return !(pointc[0] > pointa[0] || pointc[0] < pointb[0] || pointc[1] < pointa[1] || pointc[1] > pointb[1]);
}
int numberOfPairs(int** points, int pointsSize, int* pointsColSize) {int res = 0;qsort(points, pointsSize, sizeof(int *), cmp);for(int i=0; i<pointsSize; i++) {for(int j=i+1; j<pointsSize; j++) {if(points[j][1] < points[i][1]){continue;}int k=i+1;while(k<j) {if(IsPad(points[i], points[j], points[k])) break;k++;}if(k == j) res++;}}return res;
}

3027. 人員站位的方案數 ||

上面的代碼也能通過||

2 <= n <= 1000
points[i].length == 2
-109 <= points[i][0], points[i][1] <= 109
points[i] 點對兩兩不同。

// 按x降序，按y升序
int cmp(const void *a, const void *b) {int *p = *(int **)a;int *q = *(int **)b;if(p[0] == q[0]){return p[1]-q[1];} else return q[0]-p[0];
}int numberOfPairs(int** points, int pointsSize, int* pointsColSize) {int res = 0;qsort(points, pointsSize, sizeof(int *), cmp);for(int i=0; i<pointsSize; i++) {int maxY = (1e9) + 1;for(int j=i+1; j<pointsSize; j++) {if(points[j][1] < points[i][1]){continue;}// 隨著x逐漸減小，判斷中間的節點是否在i,j兩點構成的矩形內只需比較中間點的最大y值和j點的y值。如果j點y值大于中間點的最大y值，說明中間點在矩形內。if(maxY > points[j][1]) {res++;maxY = points[j][1];}}}return res;
}