自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 21:31:12，当前版本为作者最后更新于2019-07-26 14:45:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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;
}