题目大意
花花对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，他想到了一个十分有意思的题目：
首先，花花会在$x$轴正半轴和$y$轴正半轴分别挑选$n$个点。随后，他将$x$轴的点与$y$轴的点一一连接，形成$n$条线段，并保证任意两条线段不相交。花花确定这种连接方式有且仅有一种。最后，花花会给出$m$个询问。对于每个询问，将会给定一个点$P(x_p,y_p)$，问线段$OP$（$O$为坐标原点）与$n$条线段会产生多少个交点？
题目分析
根据题目要求，需要分别对$x,y$排序。
排完序后不难发现问题具有单调性，因此可以二分得到一条线段，判断这条线段是否与$OP$相交，最后即可得到交点个数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,m,a[100005],b[100005];
bool Check(int num,int x,int y) {
return (long long)-b[num]*x+(long long)b[num]*a[num]<=(long long)y*a[num];
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++)b[i]=Get_Int();
sort(a+1,a+n+1);
sort(b+1,b+n+1);
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
int Left=1,Right=n;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(mid,x,y))Left=mid+1;
else Right=mid-1;
}
printf("%d\n",Right);
}
return 0;
}
|
