2022-03-28：有一个以原点为圆心，半径为1的圆。

原创

福大大架构师每日一题

发布于 2022-03-28 21:06:19

6860

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
	}
}

执行结果如下：