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 题）

最新文章

热门文章