首页 > 代码库 > hahaha

hahaha

2024-08-19 06:12:34   207人阅读

技术分享

 

【问题描述】

　　小Q对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，他想到了一个十分有意思的题目：

　　首先，小Q会在x轴正半轴和y轴正半轴分别挑选n个点。随后，他将轴的点与轴的点一一连接，形成n条线段，并保证任意两条线段不相交。小Q确定这种连接方式有且仅有一种。最后，小Q会给出m个询问。对于每个询问，将会给定一个点p(px,py)，请回答线段OP与n条线段会产生多少个交点？

　　小Q找到了正在钻研数据结构的你，希望你可以帮他解决这道难题。

【输入格式】

　　第1行包含一个正整数n，表示线段的数量；

　　第2行包含个正整数，表示小Q在x轴选取的点的横坐标；

　　第3行包含个正整数，表示小Q在y轴选取的点的纵坐标；

　　第4行包含一个正整数m，表示询问数量；

　　随后m行，每行包含两个正整数px,py，表示询问中给定的点的横、纵坐标。

【输出格式】

　　共m行，每行包含一个非负整数，表示你对这条询问给出的答案。

【样例输入】

　　3

　　4 5 3

　　3 5 4

　　2

　　1 1

　　3 3

【样例输出】

　　0

　　3

【样例解释】

　　然后塔里啥都没有。

【数据规模与约定】

　　对于的数据，。

　　对于的数据，，坐标范围。

【题目分析】

　　把x轴和y轴上的点sort一遍，因为要保证两条线段不相交。

　　然后二分这些线段

　　判断线段是否相交的check函数，把xx1，带入要比较的线段解析式中，如果得到的Y<=yy1说明相交

#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>using namespace std;int n,m;int xx,yy;int x[200010],y[200010];bool check(int num,int xx1,int yy1){    double Y=(double)y[num]-(double)xx1*(double)y[num]/(double)x[num];    return Y<=yy1;}int main(){    freopen("hahaha.in","r",stdin);    freopen("hahaha.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&x[i]);    for(int i=1;i<=n;i++)        scanf("%d",&y[i]);    sort(x+1,x+n+1);    sort(y+1,y+n+1);    n++;    x[n]=1e9;y[n]=1e9;    scanf("%d",&m);    for(int i=1;i<=m;i++)    {        int ans=0;        scanf("%d%d",&xx,&yy);        int l=0,r=n;        while(l<=r)        {            int mid=(l+r)>>1;            if(check(mid,xx,yy)) l=mid+1,ans=max(ans,mid);            else r=mid-1;        }        printf("%d\n",ans);    }}

 

hahaha


联系
我们