【枚举】Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017) Div2C题

题目大意:

平面上有N个点(N<=1000),定义一个点为好,当且仅当,由这个点为三角形的顶点,组成的所有三角形,两边的夹角都为钝角,称为好点,求好点的数目。

题目分析:

首先考虑朴素的枚举,枚举三元组<i,j,k>,以i为顶点,j , k 为两边 ,查看是否i为顶点的所有三角形,都以i所在顶点为钝角。

考虑优化:

三角形内角和是180

如果<i, j, k> 是以i为顶点的钝角/直角三角形,则 j, k 是坏点,不需要枚举。

如果<i, j, k> 是锐角,i为坏点。

原文地址:https://www.cnblogs.com/poler/p/7479150.html