This assignment lets you get familiar with the greedy and divide-and-conquer algorithm design.you will (most likely) need to implement an efficient divide-and-conquer algorithm

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Computer Science

Assignment 2.1

 

Requirements 

This assignment lets you get familiar with the greedy and divide-and-conquer algorithm design. It is worth 5% of your total course marks.

Problem Statement: Intersecting Wires 

This problem is taken from a recent code.google.com/codejam contest. Although not required at the time the problem specifications were given, we have modified a few of the constraints so you will (most likely) need to implement an efficient divide-and-conquer algorithm to pass the CS717 harder data set.

An intranet company wants to connect two buildings with many wires, each connecting a port on the first building to a port on the second building. Wires are straight segments connecting a vertical position on the left building to a vertical position on the right building. No two wires share the same endpoint on a building. However, from our side viewpoint, some of the wires intersect midway. We also noticed that due to different tensions of the wires exactly two wires meet at any given intersection point.

On the picture below, the intersection points are the black circles, while the ports are the white circles.

The question we want to know is how many intersection points should we see given, as input, a set of pairs of vertical distances that represent wire connection points on the two buildings.

Input 

The first line of the input gives the number T of test cases. The T test cases follow. Each case begins with a line containing an integer N , denoting the number of wires you see.

The next N lines each describe one wire with two integers Ai and Bi. These describe the ports that this wire connects: Ai is the height of the port on the left building, and Bi is the height of the port on the right building.

 

Assume the following limits 1 ≤ T ≤ 1000, 1 ≤ Ai ≤ 1000000, 1 ≤ Bi ≤ 1000000 and 1 ≤ N ≤ 50000, Within each test case, all Ai and all Bi are different. No three wires intersect at the same point.

The input should be taken from keyboard/stdin/System.in. The output should be sent to console/stdout/System.out.

Sample Input:

 

2
3
1	10
5	5
7	7
2
1	1
2	2

 

Output 

We have two problems.  The first problem checks if you can read the input and compute a list of wires  that are the longest in length.  With x being the case  number,  output a single line  containing “Case  #x: ” followed by a single white-space separated list in increasing order of wires (starting at index 1).

Sample Output (longest wires): 

Case #1: 1

Case #2: 1 2

For the main problem, output one line containing “Case #x: y”, where x is the case number and y  is  the number of intersection points you see from the side vantage point.

Sample Output (number of inversions):

Case #1: 2

Case #2: 0

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of