[悬赏]奇妙的三角形

疯人￠衰人

我发完之后你改了
……
最近原则有交叉……

eff

你要先找一个最外围的节点

此方丽莎

如何找到最外围的点呢？

疯人￠衰人

三角型有一个点时外围的
那个顶角
如果对这六个点求外接多边形
那么这个顶多是多边形的一个顶点

血戮魔动冰

就问题本身而言有一个比较简单的解法……但是估计是不合格的吧……

按照X坐标对12个点排序。
分别把第123连成一个三角形
再把第456连成一个……
除非出现3个或以上X坐标相等的情况，否则不会连不出三角形…………

当然……这三角形我相信是十分有规律的……

digimondm

就单一情况有极简单的解法啊。。。

foodszhu

这个么。。。一种是暴力解法。。我们可以知道12个点。不共线。。。首先我们可以找一条直线使他们分为两块。。。（至少存在1条直线使平面内的2n点可以分为各n点的两个区域的证法。。。不用我多说吧。。。。）剩余两块再找两条线。。。分为两块。。这样平面被分为四个部分。。。每个部分3个点。。。且围成的3角型互不相交。。
（没有严格证明。。。很可能是错的。。。）但我们可以多次取不同的线总有一个满足条件。。。。（这个易知。。用反证法易推得）。。且去求这个线比较难求。。幸好只有12个点。。。故曰暴力。。。有时间证一下唯一性。。。根据实验来看有唯一性。。毕竟区域限制。。那三角形三条线都不会过别的区域去。。。
第二种么。。。从边缘点开始利用覆盖原理（其实我也不知道叫什么名字）取覆盖面积最小的一个区域。。且包括3个点。。在剩余9点中再次运行上述过程。。。递归。。。
然后就行了。。因为若还有一个点在3个点围成的区域内。。（即两三角形相交。。）则可以找到一个覆盖面积更小的点使得3点区域内无另一点。。。所以最小的覆盖即为所求。。。但不能讨论特殊情况。。。覆盖面积很好求。。            s= |(t0.x * t1.y + t1.x * t2.y + t2.x * t0.y - t1.x * t0.y - t2.x * t1.y - t0.x * t2.y)*0.5|或海伦公式即可。。第二种方法可行性比较高。。第一种方法是纯数学的。。。。用来做题还不错。。。

azrael

将所有点以X(或Y)坐标大小排序~
将排序后的点依次分为4组(顺序选取3个点)~

扩展：
以任意两点连线为基坐标~排序~获取3个点
再利用剩余点重复以上操作~
- -； 未试验过...不知是否可行...