清北NOIP2017训练营内部试题

解析在代码后面

代码

解析：二分最后一条相交线段的位置，很简单

#include

#include

#include

using namespace std;

#define N 100001

int x[N],y[N];

struct node

{

    int b;

    double k;

}Point[N];

void read(int &x)

{

    x=0; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }

}

int main()

{

    freopen("geometry.in","r",stdin);

    freopen("geometry.out","w",stdout);

    int n; read(n);

    for(int i=1;i<=n;++i) read(x[i]);

    for(int i=1;i<=n;++i) read(y[i]);

    sort(x+1,x+n+1);

    sort(y+1,y+n+1);

    for(int i=1;i<=n;i++)

    {

        Point[i].b=y[i];

        Point[i].k=-y[i]*1.0/x[i];

    }

    int m; read(m);

    int a,b; double g;

    int l,r,mid,ans;

    while(m--)

    {

        read(a); read(b);

        g=1.0*b/a;

        l=1;r=n; ans=0;

        while(l<=r)

        {

            mid=l+r>>1;

            if(Point[mid].b/(g-Point[mid].k)<=a) ans=mid,l=mid+1;

            else r=mid-1;

        }

        printf("%dn",ans);

    }

}

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com