本文共 1510 字，大约阅读时间需要 5 分钟。

【NOIP2017提高A组模拟8.10】JZOJ7月27日提高组T3 计算几何

题目描述：在x轴和y轴的正半轴上各有n个点，这2n个点要练成n条线段，要求任意两条线段不相交。有m个询问，每次询问给出点P(x, y)，问线段OP与多少条线段相交（O为原点(0,0)）。

分析：由于线段两两不相交，可以将x轴和y轴上的点从小到大排序。对于每条线段，可以求出其斜率k和截距b。对于每个询问的点P，可以求出OP的直线方程，然后找到与其他线段的交点，并判断交点是否在线段上。

代码实现：使用二分查找法快速确定交点位置，确保高效处理大量询问。代码中函数pd用于判断中间点是否满足交点条件，通过对x和y进行排序，确保线段不会相交。

题解：通过排序和二分查找，快速确定每条线段的交点位置，判断交点是否在线段上，从而计算OP与多少条线段相交。代码实现了高效的查询方法，确保在大规模数据下也能快速响应。

【题目已解答，以下为代码示例】

#include 
   
    #include 
    
     using namespace std;bool pd(int x) {    double x1, y1, kk;    kk = 1.0 * y[x] / xx;    x1 = b[x] / (kk - k[x]);    y1 = x1 * kk;    if (x1 <= x && y1 <= y) return true;    else return false;}int main() {    freopen("T3.in", "r", stdin);    freopen("T3.out", "w", stdout);    scanf("%d", &n);    for (i = 1; i <= n; i++) {        scanf("%d", &x[i]);    }    for (i = 1; i <= n; i++) {        scanf("%d", &y[i]);    }    sort(x + 1, x + n + 1);    sort(y + 1, y + n + 1);    for (i = 1; i <= n; i++) {        b[i] = y[i];        k[i] = -1.0 * y[i] / x[i];    }    scanf("%d", &m);    for (i = 1; i <= m; i++) {        scanf("%d%d", &xx, &yy);        l = 1;        r = n;        ans = 0;        while (l <= r) {            mid = (l + r) >> 1;            if (pd(mid)) {                ans = mid;                l = mid + 1;            } else {                r = mid - 1;            }        }        printf("%d\n", ans);    }    fclose(stdin);    fclose(stdout);    return 0;}
    
   

代码解释：首先读取输入，排序x和y轴上的点，然后计算每条线段的斜率和截距。对于每个询问，使用二分查找法确定OP直线与其他线段的交点，判断交点是否在线段上，返回相交的线段数量。

转载地址：http://gqql.baihongyu.com/