当前位置:网站首页>【Leetcode-每日一题】安装栅栏
【Leetcode-每日一题】安装栅栏
2022-04-23 15:25:00 【牡蛎给芝加哥带来了海】
安装栅栏
难度:困难
代码如下:
class Solution {
int[] subtraction(int[] a, int[] b) {
// 向量相减
return new int[]{
a[0] - b[0], a[1] - b[1]};
}
double cross(int[] a, int[] b) {
// 叉乘
return a[0] * b[1] - a[1] * b[0];
}
double getArea(int[] a, int[] b, int[] c) {
// 向量 ab 转为 向量 ac 过程中扫过的面积
return cross(subtraction(b, a), subtraction(c, a));
}
public int[][] outerTrees(int[][] trees) {
Arrays.sort(trees, (a, b)->{
return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
});
int n = trees.length, tp = 0;
int[] stk = new int[n + 10];
boolean[] vis = new boolean[n + 10];
stk[++tp] = 0; // 不标记起点
for (int i = 1; i < n; i++) {
int[] c = trees[i];
while (tp >= 2) {
int[] a = trees[stk[tp - 1]], b = trees[stk[tp]];
if (getArea(a, b, c) < 0) vis[stk[tp--]] = false;
else break;
}
stk[++tp] = i;
vis[i] = true;
}
int size = tp;
for (int i = n - 1; i >= 0; i--) {
if (vis[i]) continue;
int[] c = trees[i];
while (tp > size) {
int[] a = trees[stk[tp - 1]], b = trees[stk[tp]];
if (getArea(a, b, c) < 0) {
// vis[stk[tp--]] = false; // 非必须
tp--;
}
else break;
}
stk[++tp] = i;
// vis[i] = true; // 非必须
}
int[][] ans = new int[tp - 1][2];
for (int i = 1; i < tp; i++) ans[i - 1] = trees[stk[i]];
return ans;
}
}
版权声明
本文为[牡蛎给芝加哥带来了海]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_39143263/article/details/124360211
边栏推荐
- Elk installation
- Llvm - generate addition
- Nuxt project: Global get process Env information
- Practice of unified storage technology of oppo data Lake
- C语言超全学习路线(收藏让你少走弯路)
- kubernetes之常用Pod控制器的使用
- 调度系统使用注意事项
- How to write the keywords in the cover and title? As we media, why is there no video playback
- API gateway / API gateway (III) - use of Kong - current limiting rate limiting (redis)
- 如何设计一个良好的API接口?
猜你喜欢
随机推荐
如何设计一个良好的API接口?
Common interview questions of operating system:
Five data types of redis
adobe illustrator 菜单中英文对照
Thinkphp5 + data large screen display effect
JSON date time date format
Elk installation
Nuxt project: Global get process Env information
Llvm - generate for loop
Summary of interfaces for JDBC and servlet to write CRUD
Design of digital temperature monitoring and alarm system based on DS18B20 single chip microcomputer [LCD1602 display + Proteus simulation + C program + paper + key setting, etc.]
Practice of unified storage technology of oppo data Lake
Use of common pod controller of kubernetes
My raspberry PI zero 2W tossing notes record some problems encountered and solutions
The difference between having and where in SQL
Explanation of redis database (I)
Detailed analysis of SQL combat of Niuke database (26-30)
Precautions for use of dispatching system
fatal error: torch/extension.h: No such file or directory
UML learning_ Day2