nyoj 1279 （河南省第九届ACM比赛 D 题）

思路：变换一下坐标系新的坐标系就是给定的两条直线，变换之后求 x,y 都严格递增的点的个数的max；

求 x,y 都严格递增的点的个数的max，按照x的从小到大排序，x相同的按照y的从大到小排序然后对y的值进行LIS

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long int LL;
const int INF=2e9+1e8;
const int SIZE =1e5+100;

int n,a,b,c,d;
struct Point
{
    double x,y;
};
Point point[SIZE];
double dp[SIZE];
struct StraightLine
{
    double A,B,C;
};//  一条直线方程为：  A*x + B*y + C=0
bool is_inside(Point p)
{
    if(a*p.x<b*p.y&&d*p.y<c*p.x) return true;
    if(a*p.x>b*p.y&&d*p.y>c*p.x) return true;
    return false;
}
double dist(Point x,Point y)
{
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*((x.y-y.y)));
}
Point GetPoint(StraightLine x,StraightLine y) //得到两直线的交点   前提有一个交点。
{
    Point ans;
    ans.y=(y.C*x.A-x.C*y.A)/(y.A*x.B-x.A*y.B);
    ans.x=(y.C*x.B-x.C*y.B)/(x.A*y.B-y.A*x.B);
    return ans;
}
Point change(Point p)
{
    Point ans;
    StraightLine x,y;
    x.A=(double)a,x.B=(double)-b,x.C=0.;
    y.A=(double)c,y.B=(double)-d,x.C=(p.y*b-p.x*a);
    ans.x=dist(p,GetPoint(x,y));
    x.A=(double)c,x.B=(double)-d,x.C=0.;
    y.A=(double)a,y.B=(double)-b,x.C=(p.y*d-p.x*c);
    ans.y=dist(p,GetPoint(x,y));
    return ans;
}
bool cmp(Point x,Point y)
{
    if(x.x==y.x)
        return x.y>y.y;
    else return x.x<y.x;
}
int LIS(vector<double>& v)
{
    int counter=-1,len=(int)v.size();
    for(int i=0; i<=len+1; i++)
        dp[i]=1e20;
    for(int i=0; i<len; i++)
    {
        int k=lower_bound(dp,dp+len,v[i])-dp;
        dp[k]=v[i];
        counter=max(k,counter);
    }
    return counter+1;
}
int main()
{
    int ncase;
    cin>>ncase;
    while(ncase--)
    {
        scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
        int k=0;
        while(n--)
        {
            Point temp;
            scanf("%lf%lf",&temp.x,&temp.y);
            if(is_inside(temp))
            {
                point[k++]=change(temp);
            }
        }
        sort(point,point+k,cmp);
        vector<double>num;
        for(int i=0; i<k; i++)
            num.push_back(point[i].y);
        cout<<LIS(num)<<endl;
    }
    return 0;
}

nyoj 1279 （河南省第九届ACM比赛 D 题）

推荐阅读