C++14(g++5.4) 解法, 执行用时: 806ms, 内存消耗: 40532K, 提交时间: 2020-02-01 19:49:13

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int stk[N],top;
ll dp[N];
struct node
{
	ll x,y;
	int id;
}a[N];
//极角排序
bool cmp(node a,node b)
{
	ll tmp=a.x*b.y-a.y*b.x;
	if(tmp)
		return tmp>0;
	return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y;
}

ll cross(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}

int main()
{

	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&a[i].x,&a[i].y);
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	int flag,st;
	scanf("%d",&st);
	memset(dp,-1,sizeof dp);
	dp[st]=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].id==st)
		{
			flag=i;
			break;
		}
	}
	stk[++top]=flag;
	for(int i=flag+1;i<=n;i++)
	{
		if(cross(a[flag],a[i])==0) continue;
		while(top>1&&cross(a[stk[top-1]],a[stk[top]])==0)top--;
		while(top>1&&dp[a[stk[top]].id]+cross(a[stk[top]],a[i])>=dp[a[stk[top-1]].id]+cross(a[stk[top-1]],a[i]))--top;
		dp[a[i].id]=dp[a[stk[top]].id]+cross(a[stk[top]],a[i]);
		stk[++top]=i;
	}
	for(int i=1;i<=n;i++)
		printf("%lld\n",dp[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 766ms, 内存消耗: 28804K, 提交时间: 2019-06-21 21:14:52

#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define nod(x,y) (nod){x,y}
#define ll long long
using namespace std;
const int N=1e6+5;
int n,k;
int st[N],ss;
ll ans[N],p[N];
struct nod{
	int x,y,i;
}b[N];
ll cj(nod a,nod b){
	return (ll)a.x*b.y-(ll)a.y*b.x;
}
bool cmp(nod x,nod y){
	ll t=cj(x,y);
	return t>0||t==0&&x.y>y.y;
}
bool pd(nod x,nod y,nod z){
	nod X=(nod){x.x-y.x,x.y-y.y},Y=(nod){z.x-y.x,z.y-y.y};
	return cj(X,Y)<=0;
}
int main(){
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%d%d",&b[i].x,&b[i].y);
		b[i].i=i;ans[i]=-1;
	}
	scanf("%d",&k);
	stable_sort(b+1,b+n+1,cmp);
	bool go=0;
	fo(i,1,n){
		if(b[i].i==k){
			st[ss=1]=i;
			ans[k]=0;
			go=1;
			continue;
		}
		if(!go)continue;
		if(cj(b[st[1]],b[i])==0)continue;
		for(;ss>1&&pd(b[st[ss-1]],b[st[ss]],b[i]);)--ss;
		st[++ss]=i;
		ans[b[i].i]=p[ss]=p[ss-1]+cj(b[st[ss-1]],b[st[ss]]);
	}
	fo(i,1,n)printf("%lld\n",ans[i]);
}