CF249D

Miracle_1024 · 2023-07-25 08:44:16 · 题解

分析：

以 (a,b),(c,d) 为基建系，并将原来的原点也加入序列，那么题目就转化为打乱顺序之后找一个最长的 x,y 坐标都单调上升的子序列。

以 x 坐标为第一关键字，y 坐标为第二关键字降序排序，题目就转化为了找以原来的原点为结束位置的 LDS，离散化后 BIT 维护即可。

代码：

#include<bits/stdc++.h>
#define gc getchar()
#define ll long long
#define mid (l+r>>1)
#define N 100009
using namespace std;
int n,a,b,c,d,m,sta[N],top;
struct point{
    ll x,y;
    bool operator <(const point &rhs) const
    {
        return (x<rhs.x)||(x==rhs.x)&&(y>rhs.y);
    }
}p[N];
int read(){
    int x=1;
    char ch;
    while(ch=gc,ch<'0'||ch>'9'){
        if(ch=='-'){
            x-=1;
        }
    }
    int s=ch-'0';
    while(ch=gc,ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
    }
    return s*x;
}
int main(){
    n=read();
    a=read(),b=read(),c=read(),d=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        m++;
        p[m].x=(ll)y*b-(ll)x*a;
        p[m].y=(ll)x*c-(ll)y*d;
        if(p[m].x<=0||p[m].y<=0)m--;
    }
    sort(p+1,p+m+1);
    for(int i=1;i<=m;i++){
        if(!top||p[i].y>p[sta[top]].y)sta[++top]=i;
        else{
            int l=1,r=top,ret=0;
            while(l<=r){
                if(p[i].y<=p[sta[mid]].y)ret=mid,r=mid-1;
                else l=mid+1;
            }
            if(p[i].y<p[sta[ret]].y)sta[ret]=i;
        }
    }
    cout<<top<<endl;
}