链接：https://ac.nowcoder.com/acm/contest/923/D
来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
输入
5
-1 1
-1 5
1 5
0 2
2 2
5
输出
4
6
8
4
0
说明
如图所示，小w所在的基站为5号基站
示例2
输入
5
-1 1
-1 5
1 5
0 2
2 2
1
输出
0
-1
-1
-1
-1
说明
如图所示，小w所在的基站为1号基站。
由于1号基站没有出边，所以除了到自己的最小代价为0，无法到达其他基站。
示例3
输入
5
-2 2
2 2
1 1
-1 1
1 1
3
输出
4
-1
0
2
-1
说明
如图所示，小w所在的基站为3号基站，注意3号基站与2号5号基站的特征向量的叉积为0，所以没有边相连。
同理1号基站与4号基站也无边相连。
备注:
由于输入量和输出量比较大，请勿使用cin,cout进行输入输出。
本题不会卡常数，不用特地使用输入输出挂。
思路：
题意：
t=|x1*y2-x2*y1|;
输出基本点（第k个点)到其他各点最小的t值，因为基本点可以途经其他点最后到达目标点，如果无法到达目标点那么输出-1，自己到达自己则输出0，否则输出t值
步骤：
1.讲点按照与x正方向轴的夹角（点都在x轴的上半部分，点的y值均大于0）由小到大排个序（操作就在cmp中）
2.然后遍历到所在的点，这个点之前的点输出的dp值均为-1，因为x1*y2-x2*y1<0
3，从该点之后的点进行操作
4.如果suan(start,i)==0,那么该点对应为-1，直接下一个数
5.每当该点a可以到达的时候，就把该点存储起来，然后遍历下一个点b，从基本点到b的t值如果>基本点到a的最小t值加a与b的t，那么就动态更新基本点到b的值
6.最后输出每个点的dp值即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
struct node
{
ll x,y; int pos;
}s[maxn];
bool cmp(const node &x,const node &y)
{
long long temp=x.x*y.y-x.y*y.x;
if(temp)
{
return temp>;
}
else
{
return x.x*x.x+x.y*x.y>y.x*y.x+y.y*y.y;
}
}
ll suan(int i,int j)
{
return s[i].x*s[j].y-s[j].x*s[i].y;
}
ll dp[maxn]; int sta[maxn];
int main()
{
int n,pos,start,top=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld %lld",&s[i].x,&s[i].y);
s[i].pos=i;
}
memset(dp,-,sizeof(dp));
sort(s+,s++n,cmp);
scanf("%d",&pos);
for(int i=;i<=n;i++){
if(s[i].pos==pos)
{
start=i;
break;
}
}
sta[top=]=start; dp[pos]=;
for(int i=start+;i<=n;i++)
{
if(suan(start,i)==) continue;
while(top>&&suan(sta[top-],sta[top])==) --top;//防止经过一系列出栈后，栈顶点与栈顶的下一个元素的t值为0.
while(top>&&suan(sta[top],i)+dp[s[sta[top]].pos]>=suan(sta[top-],i)+dp[s[sta[top-]].pos]) --top;
dp[s[i].pos]=dp[s[sta[top]].pos]+suan(sta[top],i);//更新数值
sta[++top]=i;//栈的作用
}
for(int i=;i<=n;i++)
{
printf("%lld\n",dp[i]);
}
return ;
}