Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    lps9 22BPS1114

    Uploaded by

    Adi SEHRAWAT

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    lps9 22BPS1114

    Uploaded by

    Adi SEHRAWAT
    2 views8 pages

    Original Title

    lps9_22BPS1114

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views8 pages

    lps9 22BPS1114

    Uploaded by

    Adi SEHRAWAT

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 8

    LPS 9

    Aditya

    22BPS1114

    Q1. Given the two end points P1, P2 of a line segement P1P2, design an algorithm to
    generate n points on P1P2. Your algorithm should get the input n and accordingly output
    the x-coordinate, y-coordinate of all the n points. Analyse your algorithm with the time
    complexity.

    Answer:-

    Problem Scenario:

    Given two endpoints P1(x1,y1)P1(x_1, y_1)P1(x1,y1) and P2(x2,y2)P2(x_2, y_2)P2(x2,y2) of a


    line segment, generate nnn equidistant points on the line segment, including P1P1P1 and
    P2P2P2.

    Algorithm:

    1. Compute the di erence in x-coordinates (dxdxdx) and y-coordinates (dydydy)


    between P1P1P1 and P2P2P2.

    2. Calculate the increments (xinc,yincx_{inc}, y_{inc}xinc,yinc) for x and y coordinates


    as dx/(n−1)dx / (n-1)dx/(n−1) and dy/(n−1)dy / (n-1)dy/(n−1).

    3. Starting from P1P1P1, iteratively compute the coordinates of nnn points.

    C++ Code:-

    #include <iostream>

    #include <vector>

    #include <iomanip>

    using namespace std;

    struct Point {

    double x, y;
    };

    vector<Point> generatePoints(Point P1, Point P2, int n) {

    vector<Point> points;

    double dx = (P2.x - P1.x) / (n - 1);

    double dy = (P2.y - P1.y) / (n - 1);

    for (int i = 0; i < n; ++i) {

    points.push_back({P1.x + i * dx, P1.y + i * dy});

    return points;

    int main() {

    Point P1 = {0, 0}, P2 = {10, 10};

    int n = 5;

    vector<Point> points = generatePoints(P1, P2, n);

    cout << "Generated Points:" << endl;

    for (const auto &p : points) {

    cout << fixed << setprecision(2) << "(" << p.x << ", " << p.y << ")" << endl;

    return 0;

    Sample Input and Output:


     Input:

    o P1=(0,0)P1 = (0, 0)P1=(0,0), P2=(10,10)P2 = (10, 10)P2=(10,10), n=5n = 5n=5

     Output:

    (0.00, 0.00)

    (2.50, 2.50)

    (5.00, 5.00)

    (7.50, 7.50)

    (10.00, 10.00)

    Time Complexity:

     Time Complexity: O(n)O(n)O(n), where nnn is the number of points.

     Space Complexity: O(n)O(n)O(n), for storing the points.

    Q2. Given the two end points P1, P2 of a line segement P1P2, and the coordinates of a
    point q, design an algorithm to check whether the point q in the clockwise direction from
    the line segment P1P2 or not. Analyse your algorithm with the time complexity.

    Answer:-

    Problem Scenario:

    Given two endpoints P1(x1,y1)P1(x_1, y_1)P1(x1,y1), P2(x2,y2)P2(x_2, y_2)P2(x2,y2) of a line


    segment and a point q(x,y)q(x, y)q(x,y), check whether qqq lies in the clockwise direction
    relative to P1P2P1P2P1P2.

    Algorithm:

    1. Compute the cross product of vectors P1P2⃗\vec{P1P2}P1P2 and P1q⃗\vec{P1q}P1q


    .

    2. If the result is:

    o Positive: qqq is counterclockwise.

    o Negative: qqq is clockwise.


    o Zero: qqq lies on the line.

    C++ Code:

    #include <iostream>

    using namespace std;

    struct Point {

    double x, y;

    };

    string checkClockwise(Point P1, Point P2, Point q) {

    double crossProduct = (P2.x - P1.x) * (q.y - P1.y) - (P2.y - P1.y) * (q.x - P1.x);

    if (crossProduct < 0) return "Clockwise";

    else if (crossProduct > 0) return "Counterclockwise";

    else return "Collinear";

    int main() {

    Point P1 = {0, 0}, P2 = {4, 4}, q = {3, 2};

    cout << "Point q is " << checkClockwise(P1, P2, q) << " relative to P1P2." << endl;

    return 0;

    Sample Input and Output:


     Input:

    o P1=(0,0)P1 = (0, 0)P1=(0,0), P2=(4,4)P2 = (4, 4)P2=(4,4), q=(3,2)q = (3,


    2)q=(3,2)

     Output:

    Point q is Clockwise relative to P1P2.

    Time Complexity:

     Time Complexity: O(1)O(1)O(1), as it involves basic arithmetic.

     Space Complexity: O(1)O(1)O(1).

    Q3. Given the coordinates of n points in a 2-dimensional plane, design an algorithm to


    identify the set of points which are collinear. There may be more than one set of points
    which are collinear. Your algorithm should print all the sets of points which are collinear.
    Analyse your algorithm with the time complexity.

    Answer:-

    Problem Scenario:

    Given the coordinates of nnn points in a 2D plane, identify all sets of collinear points.

    Algorithm:

    1. For each pair of points (P1,P2)(P1, P2)(P1,P2), compute the slope mmm as
    (y2−y1)/(x2−x1)(y2 - y1) / (x2 - x1)(y2−y1)/(x2−x1).

    2. Group points with the same slope relative to P1P1P1.

    3. Check all subsets of size ≥3\geq 3≥3 for collinearity.

    C++ Code:

    #include <iostream>

    #include <vector>

    #include <map>

    #include <set>

    #include <cmath>
    using namespace std;

    struct Point {

    int x, y;

    };

    bool areCollinear(Point p1, Point p2, Point p3) {

    return (p2.y - p1.y) * (p3.x - p1.x) == (p3.y - p1.y) * (p2.x - p1.x);

    vector<vector<Point>> findCollinearPoints(vector<Point>& points) {

    vector<vector<Point>> collinearSets;

    for (size_t i = 0; i < points.size(); ++i) {

    for (size_t j = i + 1; j < points.size(); ++j) {

    vector<Point> collinear = {points[i], points[j]};

    for (size_t k = 0; k < points.size(); ++k) {

    if (k != i && k != j && areCollinear(points[i], points[j], points[k])) {

    collinear.push_back(points[k]);

    if (collinear.size() > 2) {

    collinearSets.push_back(collinear);

    }
    }

    return collinearSets;

    int main() {

    vector<Point> points = {{1, 1}, {2, 2}, {3, 3}, {4, 5}};

    vector<vector<Point>> result = findCollinearPoints(points);

    cout << "Collinear Sets:" << endl;

    for (const auto& set : result) {

    for (const auto& p : set) {

    cout << "(" << p.x << ", " << p.y << ") ";

    cout << endl;

    return 0;

    Sample Input and Output:

     Input:

    o Points: (1,1),(2,2),(3,3),(4,5)(1,1), (2,2), (3,3), (4,5)(1,1),(2,2),(3,3),(4,5)

     Output:

    Collinear Sets:

    (1, 1) (2, 2) (3, 3)

    Time Complexity:
     Time Complexity: O(n3)O(n^3)O(n3), due to nested loops for each combination.

     Space Complexity: O(n)O(n)O(n), for storing the collinear sets.

    You might also like