杭电多校第一场Leading Robots(数形结合思想)

机器人传送门
嗯…第一次完全靠自己写了一波斜率维护。。。原理不是很难，但是第一次写还是有点憨批。
首先你要处理出一个点集，这些点满足这样的条件：
任意两点得$p$不相同,并且取每个位置得最大$a$.
只有这些点才有可能对答案产生贡献。
然后还有一个注意点：就是如果对于一个位置p,如果有多个最大值a,那么这点显然产生不了贡献,但还是要做为运算过程中的一个点。
根据等式 a i t 2 / 2 + p i = a j t 2 / 2 + p j a_it^2/2+p_i=a_jt^2/2+p_j ai​t2/2+pi​=aj​t2/2+pj​
任意两点之间得相遇时间为 t 2 = ∣ p i − p j a i − a j ∣ t^2=|\frac{p_i-p_j}{a_i-a_j}| t2=∣ai​−aj​pi​−pj​​∣
现在采用数形结合思想：
令 ( a i , p i ) (a_i,p_i) (ai​,pi​)为二维坐标系上的点。
则这个相遇时间就被赋予了几何意义
即两点之间的斜率的绝对值
如果一个点要对答案产生贡献，对于位置p,显然它首先不能有多个$Max(a)$
并且对于任意 p i < p j p_ipi​<pj​和 p i > p k p_i>p_k pi​>pk​,都满足 M a x ( t i j ) < M i n ( t i k ) Max(t_{ij})Max(tij​)<Min(tik​)
接下来要做的事就是维护一个凸包了，对于Max,维护斜率绝对值递增的折线段，对于Min,维护斜率绝对值递减的折线段。
具体维护看代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100050
struct node{ll v;ll p;bool operator<(const node&ano){if(p==ano.p)return v<ano.v;return p>ano.p;}
}a[MAXN];
int b[MAXN];
double cal(int i,int j)
{return double(a[i].p-a[j].p)/double(-a[i].v+a[j].v);
}
int q[MAXN];
int mn[MAXN];
int mx[MAXN];
int ban[MAXN];
int all=0;
int main()
{int t;cin>>t;while(t--){int n;scanf("%d",&n);all=0;for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].p,&a[i].v);for(int i=1;i<=n;i++)ban[i]=0;sort(a+1,a+1+n);int cmp=0;for(int i=1;i<=n;i++){while(i+1<=n&&a[i+1].p==a[i].p)i++;if(a[i].v>cmp){cmp=a[i].v; b[++all]=i;if(a[i-1].p==a[i].p&&a[i-1].v==a[i].v)ban[all]=1;}}int l=1;int r=0;q[++r]=b[all];for(int i=all-1;i>=2;i--){//keep smallwhile(r-l>=1&&cal(b[i],q[r])>=cal(b[i],q[r-1]))r--;mn[i]=q[r];q[++r]=b[i];}l=1;r=0;q[++r]=b[1];for(int i=2;i<=all-1;i++){//keep bigwhile(r-l>=1&&cal(q[r],b[i])<=cal(q[r-1],b[i]))r--;mx[i]=q[r];q[++r]=b[i];}int ans=0;if(ban[1]==0)ans++;if(all>1&&ban[all]==0)ans++;for(int i=2;i<all;i++){if(ban[i]==0&&cal(b[i],mn[i])>cal(mx[i],b[i]))ans++;}cout<<ans<<endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！