计算几何-布布扣-bubuko.com

题目描述

华华和秀秀对计算几何有着浓厚的兴趣。他们经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，秀秀想到了一个十分有意思的题目：
首先，秀秀会在x轴正半轴y轴正半轴分别挑选n个点。随后，秀秀将x轴的点与y轴的点一一连接，形成n条线段，并保证任意两条线段互不相交。秀秀确定这种连接方式有且仅有一种。接着，秀秀给华华提出了m个问题。对于每个问题，秀秀会指定一个点P(x‘,y‘)，询问线段OP（O为坐标原点）与n条线段产生的交点数量。你能帮帮华华嘛？

输入

第1行包含一个正整数n，表示线段的数量；
第2行包含n个正整数，表示秀秀在x轴选取的点的横坐标；
第3行包含n个正整数，表示秀秀在y轴选取的点的纵坐标；
第4行包含一个正整数m，表示询问数量；
随后m行，每行包含两个正整数x‘和y‘，表示秀秀指定的各个点的横、纵坐标。

输出

共m行，每行包含一个非负整数，表示秀秀每个问题的答案。

样例输入

样例输出

0
3

提示

3条线段分别为(3,0)-(0,3),(4,0)-(0,4),(5,0)-(0,5)。(0,0)-(1,1)与他们没有交点；(0,0)-(3,3)与他们均有交点。
对于40%的数据：n,m≤10;
另有20%的数据：n,m≤100;
另有20%的数据：n,m≤1000;
对于100%的数据：n,m≤105,1≤x.y<231。

题解

　　想想怎样是线段之间没有交点？排序横坐标x和纵坐标y，然后[(x,0),(0,y)]一一对应相连，这样线段之间没有交点，然后可以构建截距式直线方程。带入输入的p点x‘坐标，求出对应的y点坐标，如果y<y‘那么就有交点，否则没用交点，为了快速计算有多少交点，使用二分（排序后的n条线段是逐渐远离原点的）。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N = 100009;
 6 typedef long long LL;
 7 LL gx[N], gy[N], x, y;
 8 int n, m;
 9 int main()
10 {
11     scanf("%d", &n);
12     for(int i = 1; i <= n; i++)
13         scanf("%lld", &gx[i]);
14     for(int i = 1; i <= n; i++)
15         scanf("%lld", &gy[i]);
16     sort(gx+1, gx+n+1);
17     sort(gy+1, gy+n+1);
18     scanf("%d", &m);
19     for(int i = 1; i <= m; i++)
20     {
21         scanf("%lld%lld", &x, &y);
22         int l = 1, r = n, ans = 0;
23         while(l <= r)
24         {
25             int mid = (l + r) >> 1;
26             LL tmp = gx[mid] * gy[mid] - gy[mid] * x;
27             if(tmp <= gx[mid]*y) ans = mid, l = mid + 1;
28             else r = mid - 1;
29         }
30         printf("%d\n", ans);
31     }
32     return 0;
33 }

View Code

技术分享图片