P1863独眼兔（题解）

· · 题解

P1863独眼兔（题解）

题目传送门

PS

此题是计算几何的入门好提，但是我却拖了大概两个月才把它搞定。。。
心情十分激动，于是来写一篇题解纪念一下QwQ。

楼上的那一篇题解都用蒟蒻我看不懂的虚数，所以这篇题解很少用用STL的东西

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{<a,b>}\times\texttt{|a|}\times\texttt{|b|} \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{<a,b>}\times\texttt{|a|}\times\texttt{|b|}，所以向量的叉积的绝对值可以表示两个向量所夹的三角形面积，向量的叉积的正负可以表示两个向量的旋转的方向。

5.此题

终于开始讲此题了。。。

一、样例解释

二、 真正的题解

总体思路是：

  1. 首先应该先找出最下面的点。
  2. 然后一个一个的去找点，找到最优的点。
  3. 最后输出答案。

但是如何去找到最优的点呢？

  1. 首先如果这个点从上一个点来需要向右旋转，那肯定不可能，这里需要用向量叉积的正负性。
  2. 然后用贪心的思想，尽量找到旋转角度最小的点，这里需要用向量叉积的模长。

所以代码出世了

上代码

#include<bits/stdc++.h>
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;
}