Computer Science
Assignment 2.1
Requirements
This assignment lets you get familiar with the greedy and divideandconquer 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 divideandconquer 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 whitespace 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
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
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. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
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
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
Get Free Quote!
316 Experts Online