P1863独眼兔（题解）
Link.
PS.
此题是计算几何的入门好题，但是我却拖了大概两个月才把它搞定。。。
心情十分激动，于是来写一篇题解纪念一下QwQ。
楼上的那一篇题解都用蒟蒻我看不懂的虚数，所以这篇题解很少用用STL的东西
Ready.
1.向量是什么
2.向量怎么表示
3.向量的产生
设$\texttt{A(x}_\texttt{1}\texttt{,y}_\texttt{1}\texttt{) B(x}_\texttt{2}\texttt{,y}_\texttt{2}\texttt{)}$
则$\overrightarrow{\texttt{AB}}=\texttt{(x}_\texttt{2}\texttt{-x}_\texttt{1}\texttt{,y}_\texttt{1}\texttt{-y}_\texttt{2}\texttt{)}$
4.向量的叉积
设$\overrightarrow{\texttt{a}}\texttt{=(x}_\texttt{1}\texttt{,y}_\texttt{1}\texttt{)}\overrightarrow{\texttt{b}}\texttt{ =(x}_\texttt{2}\texttt{,y}_\texttt{2}\texttt{)}$
$\texttt{|}\overrightarrow{\texttt{a}}\times\overrightarrow{\texttt{b}}\texttt{|=}\sin\texttt{
$\texttt{=x}_\texttt{\texttt{1}}\texttt{y}_\texttt{2}\texttt{-x}_\texttt{2}\texttt{y}_\texttt{1}$
$\boxed{\color{white}\colorbox{red}{注意：向量的叉积是一个向量，但是由于它飞出了平面，我们只考虑它的模长。}}$
由于$\texttt{|}\overrightarrow{\texttt{a}}\times\overrightarrow{\texttt{b}}\texttt{|=}\sin\texttt{
Example.
Solution.
总体思路是：
- 首先应该先找出最下面的点。
- 然后一个一个的去找点，找到最优的点。
- 最后输出答案。
但是如何去找到最优的点呢？ - 首先如果这个点从上一个点来需要向右旋转，那肯定不可能，这里需要用向量叉积的正负性。
- 然后用贪心的思想，尽量找到旋转角度最小的点，这里需要用向量叉积的模长。
Coding.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
const int INF=1000000005;
struct vec
{
int x,y;
inline vec operator+(vec &b) const {return (vec){x+b.x,y+b.y};} //向量加
inline vec operator-(vec &b) const {return (vec){x-b.x,y-b.y};} //向量减
}; //向量结构体
inline int operator*(vec a,vec b) {return a.x*b.y-a.y*b.x;} //向量的叉积
struct point
{
int x,y;
inline vec operator-(point &b) const {return (vec){x-b.x,y-b.y};} //向量产生
inline double operator/(point &b) const {return sqrt((x-b.x)*(x-b.y)+(y-b.y)*(y-b.y));} //两点之间的距离
}a[1005];//平面上的一个点
int n,w=0,vis[1005]; //vis表示此处的萝卜是否被吃掉了
vector<int>v; //v表示答案数组
int main()
{
scanf("%d",&n),a[0].x=a[0].y=INF; //第一个点设置为无穷大，是为了方便下一行处理
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),w=(a[i].y<a[w].y)?i:w;
memset(vis,0,sizeof(vis));
vis[w]=1,v.push_back(w); //最下面的点入队
point lst1=(point){0,a[w].y},lst2=a[w]; //lst1表示上一个点，lst2表示前面的第二个点
for(int i=1,mw=-1;i<n;i++,mw=-1)
{
for(int j=1;j<=n;j++)
if(!vis[j]&&(lst2-lst1)*(a[j]-lst1)>=0) //这个点没有来过且不需要享有旋转
{
if(mw==-1) {mw=j;continue;}
int t=(a[mw]-lst2)*(a[j]-lst2); //用贪心的思想，要尽量的找到与上一个面积最小
if(t<0||(t==0&&(a[j]/lst2)<(a[mw]/lst2))) mw=j;
}
if(mw==-1) break;
v.push_back(mw),vis[mw]=1,lst1=lst2,lst2=a[mw]; //加入答案序列，标位已访问
}
printf("%d ",n);
for(int i=0;i<(int)v.size();i++) printf("%d ",v[i]); //输出
return puts(""),0;
}