小w的基站网络

链接：https://ac.nowcoder.com/acm/contest/923/D
来源：牛客网

小w的基站网络

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

W城有n座基站，每座基站可用一个二维特征向量⟨x,y⟩left langle x,y ight angle⟨x,y⟩来表示，并且任意一座基站的特征向量均满足y>0。任意两座基站之间是否有单向传输数据的专线取决于这两座基站特征向量的叉积，当且仅当→a×→b>0underset{a}{ ightarrow} imes underset{b}{ ightarrow}>0a→​×b→​>0时，有一条从a基站到b基站传输数据的单向专线，专线的传输代价为这两座基站的叉积。反之如果→a×→b<=0underset{a}{ ightarrow} imes underset{b}{ ightarrow} <=0a→​×b→​<=0，则代表不能从a基站向b基站传输数据。

对于两个二维向量→a=⟨x1,y1⟩underset{a}{ ightarrow}=left langle x_{1},y_{1} ight anglea→​=⟨x1​,y1​⟩、→b=⟨x2,y2⟩underset{b}{ ightarrow}= left langle x_{2},y_{2} ight angleb→​=⟨x2​,y2​⟩

→a×→b=x1∗y2−x2∗y1underset{a}{ ightarrow} imes underset{b}{ ightarrow} = x_{1}*y_{2}-x_{2}*y_{1}a→​×b→​=x1​∗y2​−x2​∗y1​

 

每一座基站都可以传输数据和接收数据，所以当你需要从基站u向基站v传输数据时，不但可以通过u到v的单向专线（如果存在的话）直接传输数据，同时也可以先向其他基站传输数据，然后在整个基站网络的传播下到达基站v。这样的代价为经过的所有专线的代价之和。

小w在其中的第k个基站工作，他想知道他所在的基站向其他基站传输数据的最小代价各是多少。

输入描述:

第一行输入一个正整数n(1⩽n⩽106)(1leqslant n leqslant10^{6} )(1⩽n⩽106)表示有座基站。

接下来n行，每行两个整数x,y表示每个基站的特征向量⟨x,y⟩left langle x,y ight angle⟨x,y⟩，并且保证所有的特征向量均满足y∈[1,109],x∈[−109,109]yin [1,10^{9}],xin [-10^{9},10^{9}]y∈[1,109],x∈[−109,109]。

最后输入一个正整数k(1⩽k⩽n)(1leqslant k leqslant n )(1⩽k⩽n)

表示小w所在的基站。

输出描述:

输出共n行，依次表示小w所在的基站向各个基站传输数据的最小代价。如果小w所在的基站无法到达目标基站，则在该行输出一个"-1"来表示无法到达。

示例1

输入

复制

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进行输入输出。
本题不会卡常数，不用特地使用输入输出挂。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
const ll mod=1e9+7;
struct point{
    int x,y;
    int id;
    point operator - (const point &cur)const {
        return point{x-cur.x,y-cur.y};
    }
    ll operator * (const point &cur)const {
        return 1ll*x*cur.y-1ll*y*cur.x;
    }
}p[maxn],sk[maxn];
ll ans[maxn];
int n,k,st;
bool cmp(point s,point t){
    ll res=s*t;
    if(res){
        return res>0;
    }
    return s.y>t.y;
}
int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;++i){
        scanf("%d%d",&p[i].x,&p[i].y);
        p[i].id=i;
    }
    sort(p+1,p+1+n,cmp);
//    for(register int i=1;i<=n;++i){
//        printf("%d %d
",p[i].x,p[i].y);
//    }
    st=1;
    scanf("%d",&k);
    for(int i=1;i<=n;++i){
        if(p[i].id==k){
            st=i;
            break;
        }
    }
    ll cur=0;
    memset(ans,-1,sizeof(ans));
    int top=1;
    sk[top]=p[st],ans[k]=0;
    while(st<=n&&p[st]*sk[top]==0)st++;
    for(register int i=st;i<=n;++i){
        while(top>1&&(p[i]-sk[top])*(sk[top]-sk[top-1])<=0){
            cur-=(sk[top-1]*sk[top]);
            top--;
        }
        sk[++top]=p[i];
        cur+=(sk[top-1]*sk[top]);
        ans[p[i].id]=cur;
    }
    for(register int i=1;i<=n;++i){
        printf("%lld
",ans[i]);
    }
    return 0;
}