How to check if two given line segments intersect?

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.
Before we discuss solution, let us define notion of orientation. Orientation of an ordered triplet of points in the plane can be
–counterclockwise
–clockwise
–colinear
The following diagram shows different possible orientations of (a, b, c)

Note the word ‘ordered’ here. Orientation of (a, b, c) may be different from orientation of (c, b, a).
How is Orientation useful here?
Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified
1. General Case:
- (p1, q1, p2) and (p1, q1, q2) have different orientations and
- (p2, q2, p1) and (p2, q2, q1) have different orientations
2. Special Case
- (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
- the x-projections of (p1, q1) and (p2, q2) intersect
- the y-projections of (p1, q1) and (p2, q2) intersect
Examples of General Case:


Examples of Special Case:

Following is C++ implementation based on above idea.

// A C++ program to check if two given line segments intersect #include <iostream> using namespace std; struct Point { int x; int y; }; // Given three colinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true; return false; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(Point p, Point q, Point r) { int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // colinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true; // Special Cases // p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and q2 are colinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; // Doesn't fall in any of the above cases } // Driver program to test above functions int main() { struct Point p1 = {1, 1}, q1 = {10, 1}; struct Point p2 = {1, 2}, q2 = {10, 2}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; p1 = {10, 0}, q1 = {0, 10}; p2 = {0, 0}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; p1 = {-5, -5}, q1 = {0, 0}; p2 = {1, 1}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; return 0; }

Output:

No
Yes
No

Sources:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf

Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

Example:

set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}

For simplicity, we have assumed that the given set is sorted. We can always add a pre-processing step to first sort the set and then apply the below algorithms.

A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n³) time.

Dynamic  Programming algorithm:
Refer the paper http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf
Let us first look at
Given a sorted set, find if there exist three elements in Arithmetic Progression or not

algorithm-
The answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]‘ and ‘set[k]‘ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1.
How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
1) Initialize i as j-1 and k as j+1
2) Do following while i >= 0 and j <= n-1
..........a) If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b) If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c) Else if set[i] + set[k] < 2*set[j], then increment k (do k++).

Program:
#include <iostream>
using namespace std;

// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted
bool arithmeticThree(int set[], int n)
{
    // One by fix every element as middle element
    for (int j=1; j<n-1; j++)
    {
        // Initialize i and k for the current j
        int i = j-1, k = j+1;

        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2*set[j])
                return true;
            (set[i] + set[k] < 2*set[j])? k++ : i--;
        }
    }

    return false;
}
 int main()
{
    int set1[] = {1, 7, 10, 15, 27, 29};
    int n1 = sizeof(set1)/sizeof(set1[0]);
    arithmeticThree(set1, n1)? cout << "Yes\n" : cout << "No\n";

    int set2[] = {1, 7, 10, 15, 27, 28};
    int n2 = sizeof(set2)/sizeof(set2[0]);
    arithmeticThree(set2, n2)? cout << "Yes\n" : cout << "No\n";
    return 0;
}
How to extend the above solution for the original problem? algorithm-
If the given set has two or more elements, then the value of LLAP is at least 2.The idea is to create a 2D table L[n][n]. An entry L[i][j] in this table stores LLAP with set[i] and set[j] as first two elements of AP and j > i. The last column of the table is always 2. Rest of the table is filled from bottom right to top left. To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.

Program:

// C++ program to find Length of the Longest AP (llap) in a given sorted set. #include <iostream> using namespace std; // Returns length of the longest AP subset in a given set int lenghtOfLongestAP(int set[], int n) {     if (n <= 2) return n; //Only valid entries are the entries where j>i     int L[n][n];     int llap = 2; // Initialize the result // Fill entries in last column as 2. There will always be // two elements in AP with last number of set as second // element in AP     for (int i = 0; i < n; i++)         L[i][n-1] = 2; // Consider every element as second element of AP     for (int j=n-2; j>=1; j--)     { // Search for i and k for j         int i = j-1, k = j+1;         while (i >= 0 && k <= n-1)         {             if (set[i] + set[k] < 2*set[j])                 k++; // Before changing i, set L[i][j] as 2             else if (set[i] + set[k] > 2*set[j])             {                 L[i][j] = 2, i--;             }             else             { // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side                 L[i][j] = L[j][k] + 1; // Update overall LLAP, if needed                 llap = max(llap, L[i][j]); // Change i and k to fill more L[i][j] values for // current j                 i--;                 k++;             }         } // If the loop was stopped due to k becoming more than // n-1, set the remaining entties in column j as 2         while (i >= 0)         {             L[i][j] = 2;             i--;         }     }     return llap; } int main() {     int set1[] = {1, 7, 10, 13, 14, 19};     int n1 = sizeof(set1)/sizeof(set1[0]);     cout << lenghtOfLongestAP(set1, n1) << endl;     int set2[] = {1, 7, 10, 15, 27, 29};     int n2 = sizeof(set2)/sizeof(set2[0]);     cout << lenghtOfLongestAP(set2, n2) << endl;     int set3[] = {2, 4, 6, 8, 10};     int n3 = sizeof(set3)/sizeof(set3[0]);     cout << lenghtOfLongestAP(set3, n3) << endl;     return 0; }

Output:

4
3
5

Time Complexity: O(n²)
Auxiliary Space: O(n²)

 

Ciel and Dancing

http://codeforces.com/problemset/problem/322/A

Fox Ciel and her friends are in a dancing room. There are n boys and m girls here, and they never danced before. There will be some songs, during each song, there must be exactly one boy and one girl are dancing. Besides, there is a special rule:

• either the boy in the dancing pair must dance for the first time (so, he didn't dance with anyone before);
• or the girl in the dancing pair must dance for the first time.

Help Fox Ciel to make a schedule that they can dance as many songs as possible.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of boys and girls in the dancing room.

Output

In the first line print k — the number of songs during which they can dance. Then in the following k lines, print the indexes of boys and girls dancing during songs chronologically. You can assume that the boys are indexed from 1 to n, and the girls are indexed from 1 to m.

Sample test(s)

Input

2 1

Output

2
1 1
2 1

Input

2 2

Output

3
1 1
1 2
2 2

Note

In test case 1, there are 2 boys and 1 girl. We can have 2 dances: the 1st boy and 1st girl (during the first song), the 2nd boy and 1st girl (during the second song).
And in test case 2, we have 2 boys with 2 girls, the answer is 3.


Program:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<n+m-1<<endl;
    for(int i=1;i<=m;i++)
    {
        cout<<"1 "<<i<<endl;
    }
    for(int i=2;i<=n;i++)
    {
        cout<<i<<" 1"<<endl;
    }
    return 0;
}

create a BST from a given level order traversal

ALGORITHM:
The first elenment is the root.All elements less than first element in the level order traversal belong to left subtree and appear in the same order as the level order traversal of left subtree.Similarly, for the right subtree.

We use recursion in a function returning the pointer to the root of the tree on passing an array containing the level order traversal .The base case is if the level order array is empty we return a NULL tree.Otherwise, we create a tree with head as the first element of the array, then we segregate all elements less than and greater than the first element in the left and right array respectively.These are the level order traversals of the left and right subtrees respectively.These are passed to the function and return the head pointers of the eft and right subtrees that are assigned to tree->left and tree-> right.

Program:
#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct tree
{
    int d;
    struct tree* left;
    struct tree* right;
};
struct tree* create_bst(int a[100],int n)
{
    if(n==0)
    {
        return NULL;
    }
    struct tree* head=(struct tree*)malloc(sizeof(struct tree));
    int l[100];
    int r[100];
    head->d=a[0];
    int j=0,k=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[0])
        {
            l[j++]=a[i];
        }
        else
        {
            r[k++]=a[i];
        }
    }
    head->left=create_bst(l,j);
    head->right=create_bst(r,k);
    return head;
}
void print_in(struct tree* head)
{
    if(head!=NULL)
    {
        print_in(head->left);
        printf("%d ",head->d);
        print_in(head->right);
    }
}
int main()
{
    struct tree*head;
    int a[100];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("hi");
    head=create_bst(a,n);
    printf("hi");
    print_in(head);
}


Time comlexity:
Worst case:n^2
Best case:nlogn [T(n)=2T(n/2)+O(n)]

Design a stack with operations on middle element

How to implement a stack which will support following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element

Deleting an element from middle is not O(1) for array.In singly linked list, moving middle pointer in both directions is not possible. The idea is to use Doubly Linked List (DLL). We can delete middle element in O(1) time by maintaining mid pointer. We can move mid pointer in both directions using previous and next pointers.

If there are even elements in stack, findMiddle() returns the first middle element. For example, if stack contains {1, 2, 3, 4}, then findMiddle() would return 2.

/* Program to implement a stack that supports findMiddle() and deleteMiddle
in O(1) time */
#include <stdio.h>
#include <stdlib.h>
/* A Doubly Linked List Node */
struct DLLNode
{
    struct DLLNode *prev;
    int data;
    struct DLLNode *next;
};
/* Representation of the stack data structure that supports findMiddle()
in O(1) time. The Stack is implemented using Doubly Linked List. It
maintains pointer to head node, pointer to middle node and count of
nodes */
struct myStack
{
    struct DLLNode *head;
    struct DLLNode *mid;
    int count;
};
void print(struct myStack*ms)
{
    struct DLLNode *temp=ms->head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
/* Function to create the stack data structure */
struct myStack *createMyStack()
{
    struct myStack *ms =(struct myStack*)malloc(sizeof(struct myStack));
    ms->head=NULL;
    ms->count = 0;
    return ms;
};
/* Function to push an element to the stack */
void push(struct myStack *ms, int new_data)
{
    /* allocate DLLNode and put in data */
    struct DLLNode* new_DLLNode =(struct DLLNode*) malloc(sizeof(struct DLLNode));
    new_DLLNode->data = new_data;
    /* Since we are adding at the begining,
    prev is always NULL */
    new_DLLNode->prev = NULL;
    /* link the old list off the new DLLNode */
    new_DLLNode->next = ms->head;
    /* Increment count of items in stack */
    ms->count += 1;
    /* Change mid pointer in two cases
    1) Linked List is empty
    2) Number of nodes in linked list is odd */
    if (ms->count == 1)
    {
        ms->mid = new_DLLNode;
    }
    else
    {
        ms->head->prev = new_DLLNode;
        if (ms->count & 1) // Update mid if ms->count is odd
            ms->mid = ms->mid->prev;
    }
    /* move head to point to the new DLLNode */
    ms->head = new_DLLNode;
}
int deletemid(struct myStack *ms)
{
    struct DLLNode* m=ms->mid;
    if(m!=NULL)
    {
        if(ms->count==1)
        {
            ms->mid=NULL;
            ms->head=NULL;
        }
        ms->count--;
        if(m->prev!=NULL)
        {
            m->prev->next=m->next;
        }
        if(m->next!=NULL)
        {
            m->next->prev=m->prev;
        }
        if(ms->count%2==0)
        {
            ms->mid=m->next;
        }
        else if(ms->count%2!=0)
        {
            ms->mid=m->prev;
        }
        free(m);
    }
}
/* Function to pop an element from stack */
int pop(struct myStack *ms)
{
    /* Stack underflow */
    if (ms->count == 0)
    {
        printf("Stack is empty\n");
        return -1;
    }
    struct DLLNode *head = ms->head;
    int item = head->data;
    ms->head = head->next;
// If linked list doesn't become empty, update prev
// of new head as NULL
    if (ms->head != NULL)
        ms->head->prev = NULL;
    ms->count -= 1;
// update the mid pointer when we have even number of
// elements in the stack, i,e move down the mid pointer.
    if (!((ms->count) & 1 ))
        ms->mid = ms->mid->next;
    free(head);
    return item;
}
// Function for finding middle of the stack
int findMiddle(struct myStack *ms)
{
    if (ms->count == 0)
    {
        printf("Stack is empty now\n");
        return -1;
    }
    return ms->mid->data;
}
// Driver program to test functions of myStack
int main()
{
    /* Let us create a stack using push() operation*/
    struct myStack *ms = createMyStack();
    char c[2]="a";
    int n;
    while(c[0]!='q')
    {
        scanf("%s",c);
        if(c[0]=='i')
        {
            scanf("%d",&n);
            push(ms,n);
            print(ms);
            continue;
        }
        if(c[0]=='p')
        {
            pop(ms);
            print(ms);
        }
        if(c[0]=='m')
        {
            n=findMiddle(ms);
            if(n!=-1)
            {
                printf("%d\n",n);
            }
            print(ms);
        }
        if(c[0]=='d')
        {
            deletemid(ms);
            print(ms);
        }
    }
    return 0;
}

 

Program to count leaf nodes in a binary tree

getLeafCount(node)
1) If node is NULL then return 0.
2) Else If left and right child nodes are NULL return 1.
3) Else recursively calculate leaf count of the tree using below formula.
    Leaf count of a tree = Leaf count of left subtree + 
                                 Leaf count of right subtree

Implementation:

#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Function to get the count of leaf nodes in a binary tree*/ unsigned int getLeafCount(struct node* node) { if(node == NULL) return 0; if(node->left == NULL && node->right==NULL) return 1; else return getLeafCount(node->left)+getLeafCount(node->right); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /*Driver program to test above functions*/ int main() { /*create a tree*/ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /*get leaf count of the above created tree*/ printf("Leaf count of the tree is %d", getLeafCount(root)); getchar(); return 0; }

Time Complexity : O(n)
Proof:
T(n) = T(k) + T(n – k – 1) + c
Where k is the number of nodes on one side of root and n-k-1 on the other side.
Let’s do analysis of boundary conditions
Case 1: Skewed tree (One of the subtrees is empty and other subtree is non-empty )
k is 0 in this case.
T(n) = T(0) + T(n-1) + c
T(n) = 2T(0) + T(n-2) + 2c
T(n) = 3T(0) + T(n-3) + 3c
T(n) = 4T(0) + T(n-4) + 4c
…………………………………………
………………………………………….
T(n) = (n-1)T(0) + T(1) + (n-1)c
T(n) = nT(0) + (n)c
Value of T(0) will be some constant say d. (traversing a empty tree will take some constants time)
T(n) = n(c+d)
T(n) = (-)(n) (Theta of n)
Case 2: Both left and right subtrees have equal number of nodes.
T(n) = 2T(|_n/2_|) + c
This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method http://en.wikipedia.org/wiki/Master_theorem. If we solve it by master method we get (-)(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Find The Maximum Sum in Triangle From Top to Bottom (Euler Problem).

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Brute Force

When answering the problem with a brute force solution, it is pretty simple to go through the steps, we just need to try all combinations. Since we have a binary choice each time. We can iterate through all possibilities with a normal integer counter, and use the bits of the number to pick the direction left or right. While running through the path, we sum up the numbers and check if they are larger than the current maximum found.It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all.

Dynamic Programming

 
Standing at the top of the triangle we have to choose between going left and right. In order to make the optimal choice (which maximizes the sum), we would have to know how large a sum we can get if we go either way. We have to solve the two smaller problems which I have marked with blue and the orange in the figure to the right.


We can break each of the sub-problems down in a similar way, and we can continue to do so until we reach a sub-problem at the bottom line consisting of only one number, then the answer is the number it self. Once that question is answered we can move up one line, and answer the questions posed there with a solution which is a + max(b,c).
Once we know the answer to all 3 sub-problems on the next to last line, we can move up and answer the posed sub-problems by the same formula already applied. And we can continue to do so until we reach the original question of whether to go left or right

Savings with Dynamic Programming

If we want to solve the small problem with brute force, we would need to test all 8 paths, each resulting in 3 additions, in total 24 additions.
If we use dynamic programming, the first iteration would require 3 maximum comparison operations and 3 additions. The next line would require 2 maximum comparison operations and 2 additions, and the first line would require one of each. So a total of 6 maximum comparison operations and 6 additions.

Dynamic Programming – The Algorithm

We can make a short-cut with the algorithm, as we don’t have to break the problem into sub-problems, but can start from the bottom and work the way up through the triangle until we reach the top and the algorithm spits out a number.
We start with a triangle that looks like

3
7 4
2 4 6
8 5 9 3

Applying the algorithm to the small problem we will need three iterations. The first iteration we apply the rule a + max(b,c) which creates a new triangle which looks as

3
7 4
10 13 15

Making the second iteration of the algorithm makes the triangle look

3
20 19

And if we run the algorithm once more, the triangle collapses to one number – 23 – which is the answer to the question.

Program:

#include<stdio.h>
int main(void)
{
    int j,t,n,i,a[100][100];
    printf("hi\n");
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=0;j<=i;j++)
            {
                a[i][j]+=a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
            }
        }
        printf("%d\n",a[0][0]);
    }
    return 0;
}
Time complexity:O(n^2) where n is the number of rows.
we traverse through  n-1  elements on (n-2)th line, (n-2) elements on (n-3)th line and so on till 1 element in first line, a total of 1+2+..+(n-1) elements i.e. (n-1)n/2 or O(n^2) eelments.
At each element, an adition and comparision operation is performed in O(1) time.