CF249D 题解

· · 题解

题意

坐标系上给出 n 个点，第 i 个点为 (x_i,y_i) 且这些点两两不同。求最多有多少个点依次连成的折线上的线段的斜率在 \frac ab 到 \frac cd 之间（不包括 \boldsymbol{\frac ab} 和 \boldsymbol{\frac cd}）。折线必须从坐标原点开始且坐标原点不计入答案。1\le n,x_i,y_i\le 10^5,\boldsymbol{0\le}\ a,b,c,d\le 10^5,\frac ab<\frac cd。

解法

考虑把两个点的斜率用另一种方式表示：i 和 j 之间的斜率在 \frac ab 和 \frac cd 之间可以表示如下：

定义向量 \overrightarrow {e_1}=(b,a),\overrightarrow {e_2}=(d,c)，同时将 \overrightarrow{ij} 表示为 a\overrightarrow{e_1}+b\overrightarrow{e_2}（其中 a 和 b 为常数），则从 i 点到 j 点能延伸一条折线当且仅当 a>0,b>0。证明显然。

同时令原点为 O，则 \overrightarrow{ij}=\overrightarrow{Oj}-\overrightarrow{Oi}。故而可以对于第 i 个点，处理 A_i,B_i 满足 \overrightarrow{Oi}=A_i\overrightarrow{e_1}+B_i\overrightarrow{e_2}。可得 B_i=\frac{y_ib-x_ia}{cb-ad},A_i=\frac{x_ic-y_id}{cb-ad}。（注意有解对应了 \frac cd>\frac ab，也就是 cb>ad，故而可以只需要维护 y_ib-x_ia 和 x_ic-y_id 之间的大小关系）这样可以令 dp_i 为 O 点到 i 点的最长折线长度，则转移方程有 dp_i=\max_{A_i-A_j>0\text{ and }B_i-B_j>0}(dp_j)+1。直接用树状数组统计二维偏序即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,i,a,b,c,d,x,y; 
struct Vals{
    long long val;
    int idx;
    inline bool operator <(const Vals &p)const{return val<p.val;}
}A[maxn],B[maxn];
struct node{
    int ra,rb;
    inline bool operator <(const node &p)const{
        if(ra!=p.ra) return ra<p.ra;
        return rb<p.rb; 
    }
}N[maxn];
int C[maxn],dp[maxn];
inline void Add(int p,const int &v){
    for(;p<maxn;p+=(p&-p)) C[p]=max(C[p],v);
}
inline int Que(int p){
    int ret=0;
    for(;p;p&=(p-1)) ret=max(ret,C[p]);
    return ret;
}
long long lst;
int main(){
    scanf("%d",&n);
    scanf("%d/%d%d/%d",&a,&b,&c,&d);
    for(i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        A[i].idx=B[i].idx=i;
        B[i].val=(1LL*y*b)-(1LL*x*a);
        A[i].val=(1LL*x*c)-(1LL*y*d);
    }
    sort(A+1,A+n+1);sort(B+1,B+n+1);
    for(i=1;A[i].val<=0;++i);
    x=1;lst=A[i].val; 
    for(;i<=n;++i){
        while(A[i].val==lst) N[A[i++].idx].ra=x;
        lst=A[i].val;N[A[i].idx].ra=++x;
    }
    for(i=1;B[i].val<=0;++i);
    x=1;lst=B[i].val;
    for(;i<=n;++i){
        while(B[i].val==lst) N[B[i++].idx].rb=x;
        lst=B[i].val;N[B[i].idx].rb=++x;
    }
    sort(N+1,N+n+1);x=1;a=0;
    for(i=1;!N[i].ra;++i);
    for(;i<=n;++i){
        if(N[i].ra!=N[x].ra) for(;x<i;++x) if(N[x].rb) Add(N[x].rb,dp[x]);
        if(N[i].rb) a=max(a,dp[i]=Que(N[i].rb-1)+1);
    }
    printf("%d",a);
    return 0;
}