(5/5)

Hire Me
(5/5)

Hire Me
(5/5)

Hire Me
(5/5)

Hire Me

# 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

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

## Related Questions

##### . The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

##### . 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

##### . The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

##### . Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

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

##### . The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme

Get Free Quote!

299 Experts Online