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
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
