团体程序设计天梯赛-L3-021 神坛 的一些错误做法 和 一些想法

https://pintia.cn/problem-sets/994805046380707840/problems/994805046577840128

错误做法:

极角排序 + 最小三角形的两边是极角相邻的

错误原因:

向量:

AB (x1,y1)

AC (x2,y2)

三角形面积:

| y2*x1 - y1*x2 |

 而极角排序为:(叉积)

向量OA(x1,y1) OB(x2,y2)

y2*x1>y1*x2,则B点排在A点后面

但不能满足:

向量OA(x1,y1) OB(x2,y2) OC(x3,y3)

y3*x1-y1*x3>y2*x1-x1*y2

样例:

input:

6
0 -2
-1 0
1 0
0 50
-50 -50
50 -50


output:

2.000

wrong output:

26.000

一些想法:

 通过一些边来缩短某些边的作用范围(另外一条边在某个角度范围内选择,这条边与另外一条边共用一个端点),不过时间复杂度仍然很高,

 

单调队列想过,不过难以实现。确定一个旋转方向,前面的边在角度很大时才起作用,但是顺序并不是连续的。同时,无法确定一条边的作用域,其不仅仅由相邻的边来决定。

 

原文地址:https://www.cnblogs.com/cmyg/p/9559796.html