2022-03-28:有一个以原点为圆心,半径为1的圆。
在这个圆的圆周上,有一些点,
因为所有的点都在圆周上,所以每个点可以有很简练的表达。
比如:用0来表示一个圆周上的点,这个点就在(1,0)位置,
比如:用6000来表示一个点,这个点是(1,0)点沿着圆周逆时针转60.00度之后所在的位置,
比如:用18034来表示一个点,这个点是(1,0)点沿着圆周逆时针转180.34度之后所在的位置,
这样一来,所有的点都可以用[0, 36000)范围上的数字来表示。
那么任意三个点都可以组成一个三角形,返回能组成钝角三角形的数量。
来自hulu。
答案2022-03-28:
半圆同侧两点必然是钝角三角形。
时间复杂度:排序的。
代码用golang编写。代码如下:
package main
import (
"fmt"
"sort"
)
func main() {
arr := []int{10000, 20000, 30000, 10100, 10200}
ret := obtuseAngles(arr)
fmt.Println(ret)
}
func obtuseAngles(arr []int) int {
// n长度的排序,O(N * logN)
// O(N)
n := len(arr)
m := n << 1
enlarge := make([]int, m)
sort.Ints(arr)
for i := 0; i < n; i++ {
enlarge[i] = arr[i]
enlarge[i+n] = arr[i] + 36000
}
ans := 0
// 这里不用二分查找(太慢),能做一个不回退的优化
for L, R := 0, 0; L < n; L++ {
for R < m && enlarge[R]-enlarge[L] < 18000 {
R++
}
ans += num(R - L - 1)
}
return ans
}
func num(nodes int) int {
if nodes < 2 {
return 0
} else {
return ((nodes - 1) * nodes) >> 1
}
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2021_12_4_week/Code03_HowManyObtuseAngles.java)