《编程珠玑》第4章习题---确定包围点的线段

1.问题描述

对实数构成的数组定义了条直线。当位于内时,对于区间内的所有,这些线段按排序。用更形象的话来说,这些线段在垂直方向上不交叉。给定一个满足的点,确定包围这个点的两条线段。

2.分析

  • 首先实数对是按照一种从下至上的几何顺序排列的,其实就是有序数组。
  • 寻找包围这个点的两条线段就是在有序数组中找到最后一个目标和第一个目标的位置。
  • 对有序数组的搜寻一般使用二分搜索这个高效的方法。

3.实现代码

  • 我的C++代码如下:

    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    #include<iostream>
    #include<vector>
    using namespace std;

    //x在直线line上方就返回true, 否则返回false
    bool isAbove(const pair<double, double>& line, const pair<double, double>& x){
    return x.second > x.first * line.first + line.second;
    }

    //x在直线line上就返回true, 否则返回false
    bool isOn(const pair<double, double>& line, const pair<double, double>& x){
    return x.second == x.first * line.first + line.second;
    }

    //x在直线line上就返回true, 否则返回false
    bool isBelow(const pair<double, double>& line, const pair<double, double>& x){
    return x.second < x.first * line.first + line.second;
    }

    //找到第一个不小于x的元素的下标
    int findFirstAbove(const vector<pair<double, double>>& lines, const pair<double, double>& x){
    int l = 0, u = lines.size() - 1;
    if(isAbove(lines[u], x)){
    return -1;
    }
    int result = u;
    while(l <= u){
    int mid = l + (u - l) / 2;
    //中间值不小于x, result一定在[l, u)之间
    if(!isAbove(lines[mid], x)){
    result = mid;
    u = mid - 1;
    } else{
    l = mid + 1;
    }
    }
    return result;
    }

    void betweenTwoLine(const vector<pair<double, double>>& lines, const pair<double, double>& x){
    int index = findFirstAbove(lines, x);
    if(index == -1){
    cout << "All the lines are below the point!" << endl;
    } else if(index == 0 && isBelow(lines[index], x)){
    cout << "All the lines are below the point!" << endl;
    } else if(isOn(lines[index], x)){
    printf("The point is on the line y = %f x + %f\n", lines[index].first, lines[index].second);
    } else{
    printf("The point is between line y = %f x + %f and y = %f x + %f\n",
    lines[index - 1].first, lines[index - 1].second,
    lines[index].first, lines[index].second);
    }
    }

    int main(){
    vector<pair<double, double>> lines = {{0.1, 0.1}, {-0.1, 0.4}, {0, 0.5}, {0.1, 0.6}, {-0.1, 0.9}, {0, 1}};
    pair<double, double> target = {0.5, 0.48};
    betweenTwoLine(lines, target);
    return 0;
    }
------------- 本文结束 感谢您的阅读 -------------

本文标题:《编程珠玑》第4章习题---确定包围点的线段

文章作者:Perry

发布时间:2019年07月23日 - 23:22

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/c06b915.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%