program讲解 、C++程序语言辅导
Purpose
The purpose of this assignment is for you to:
• Design efficient algorithms in pseudocode.
• Improve your proficiency in C programming and your dexterity with dynamic
memory allocation.
• Demonstrate understanding of a representing problems as graphs and
implementing a set of algorithms.
Convex Hull
What is a convex hull?
A convex hull is a concept from geometry and computational geometry that refers to
the smallest convex set that contains a given set of points in a Euclidean space. Imagine
you have a set of nails sticking out from a board; the convex hull is the shape you would
get by stretching a rubber band around all the nails and letting it snap tight around
them. The boundary created by the rubber band defines the convex hull.
More formally, a convex set is a set of points in which, for any two points within the set,
the line segment connecting them lies entirely within the set. The convex hull of a set of
points is then the smallest convex set that contains all those points. It is often visualized
in two dimensions (2D) but can be extended to higher dimensions as well.
Computing the convex hull is a foundational problem in computational geometry
because it is a precursor to solving many other problems, such as finding the closest
pair of points, and solving various optimization problems. Several algorithms exist for
computing the convex hull, with their efficiency depending on the specific dimensions
and characteristics of the point set. Examples of such algorithms include Graham's scan
and Jarvis's march (also known as the gift wrapping algorithm) among others.
Applications
Convex hulls have numerous real-world applications. Some of the typical applications
include:
• Image Processing and Computer Vision: Convex hulls are used in image
processing for object detection, recognition, and segmentation. They help in
identifying the outer boundary of objects and separating foreground objects
from the background.
• Geographic Information Systems (GIS): In GIS, convex hulls are utilized for
spatial analysis, such as identifying the boundary of a geographic region or
finding the convex hull of a set of spatial data points.
• Robotics and Path Planning: Convex hulls play a vital role in robotics for path
planning, obstacle avoidance, and navigation. They help robots efficiently
navigate through complex environments by identifying obstacles and
determining safe paths.
• Collision Detection in Physics Simulations: In physics simulations and video
games, convex hulls are used for collision detection between objects. They help
determine if two objects intersect or collide with each other.
• Pattern Recognition: Convex hulls are employed in pattern recognition tasks,
such as hand-written character recognition, signature verification, and
fingerprint matching. They aid in extracting important features and reducing the
dimensionality of data.
Convex Hull Computation Algorithms
Jarvis March
• Initialization:
o Start by selecting the leftmost point among the given points as the
starting point of the convex hull. If there are multiple leftmost points,
choose the one with the lowest y-coordinate.
o Add this point to the convex hull.
• March:
o Iterate through all the points to find the next point on the convex hull.
o To find the next point, start from the current point and choose the point
that has the largest counterclockwise angle with respect to the current
point.
o This is done by comparing the slopes of the line segments formed by
the current point and each of the other points.
o The point with the largest counterclockwise angle is the next point on
the convex hull.
o Add this next point to the convex hull.
• Termination:
o Repeat the main loop until the next point on the convex hull is the same
as the starting point.
o Once the next point becomes the starting point, the algorithm
terminates.
• Output:
o The output of the algorithm is the list of points that form the convex
hull, ordered in counterclockwise order.
The time complexity of the Jarvis March algorithm is O(nh), where n is the number of
input points and h is the number of points on the convex hull. In the worst case, where
all points are on the convex hull, the time complexity is O(n^2).
Pseudocode
JarvisMarch(points):
// Ensure there are at least 3 points
if length(points) < 3:
return empty convex hull
// Initialize an empty list to store convex hull points
convexHull <- empty list
// Find the leftmost point (pivot) among the given points
leftmost <- leftmost_point(points)
// Start from the leftmost point
current <- leftmost
repeat:
// Add current point to the convex hull
add current to convexHull
// Find the next point 'nextPoint' such that it forms a counterclockwise turn
// with the current point and any other point in the set
nextPoint <- points[0]
for each point in points:
if orientation(nextPoint, current, point) == counterclockwise:
nextPoint <- point
// Set 'nextPoint' as the current point for the next iteration
current <- nextPoint
// Repeat until we return to the starting point (leftmost)
until current == leftmost
// Return the list of points in the convex hull
return convexHull
Notes
• leftmost_point(points) returns the point with the lowest x-coordinate (or the
bottom-most point satisfying this condition in case of ties).
• orientation(p, q, r) is a function that determines the orientation of three points.
It returns:
o 0 if the points are collinear.
o 1 if they form a clockwise turn.
o 2 if they form a counterclockwise turn.
Example
In the above example, the starting point is identified as point 8. We examine each point
in relation to point 8, determining which one results in the greatest counterclockwise
turn compared to the rest. To put it more straightforwardly, the goal is to locate a point
that ensures the line segment from the previous to the current point remains on the left
side, while all other points are positioned to the right. As observed, point 5 is the initial
choice because the line segment from point 8 to point 5 generates the most significant
counterclockwise angle in comparison to the others. Following this logic, when
positioned at point 5, we evaluate all other points and select point 2 as the one that
yields the most pronounced counterclockwise turn. The process continues in this
manner until it returns to the starting point, which is point 8.
Graham's scan
• Initialization:
o Start by selecting the point with the lowest y-coordinate (or the leftmost
point in case of ties) as the pivot point.
o Sort the remaining points based on their polar angles with respect to the
pivot point. If two points have the same polar angle, the one closer to
the pivot point should come first.
• Scan:
o Iterate through the sorted points and add them to the convex hull one
by one.
o For each point, check if it forms a counterclockwise turn with the two
previously added points on the convex hull.
o If it forms a counterclockwise turn, add the point to the convex hull.
Otherwise, remove the last point from the convex hull until a
counterclockwise turn is formed.
o Repeat this process until all points are scanned.
• Termination:
o Once all points are scanned, the convex hull is complete.
• Output:
o The output of the algorithm is the list of points that form the convex
hull, ordered in counterclockwise order.
The time complexity of Graham's scan algorithm is O(nlogn), where n is the number of
input points. This complexity arises from the sorting step required to order the points
based on their polar angles. The scanning step, where each point is checked and added
to the convex hull, takes linear time.
GrahamScan(points):
// Ensure there are at least 3 points
if length(points) < 3:
return empty convex hull
// Find the point with the lowest y-coordinate
lowest = point with lowest y-coordinate in points
// Sort the points based on their polar angles with respect to the lowest point
sort points by polar angle with respect to lowest
// Initialize an empty stack to store convex hull points
stack = empty stack
// Push the first three points to the stack
push points[0] to stack
push points[1] to stack
push points[2] to stack
// Iterate over the remaining points
for i = 3 to length(points):
// While the current point and the two points below the top of the stack
// make a non-left turn, pop the top of the stack
while orientation(second_top(stack), top(stack), points[i]) != counterclockwise:
pop top of stack
// Push the current point to the stack
push points[i] to stack
// The stack now contains the convex hull points
return stack
Notes
• lowest represents the point with the lowest y-coordinate in the set of points.
• sort points by polar angle with respect to lowest sorts the points based on
their polar angles with respect to the lowest point. If two points have the same
polar angle, the one closer to the lowest point comes first.
• second_top(stack) returns the second topmost point in the stack.
• orientation(p, q, r) is a function that determines the orientation of three points.
It returns:
o 0 if the points are collinear.
o 1 if they form a clockwise turn.
o 2 if they form a counterclockwise turn.
Example
In the above example, point 0 is identified as the point with the lowest y-coordinate.
Subsequently, the other points are arranged based on their polar angles relative to
point 0. Initially, points 0, 1, and 2 are placed into the stack. The addition of point 3 to
the stack occurs because it facilitates a left turn in relation to the preceding two points
(points 2 and 1). Conversely, point 4 induces a right turn compared to the last two
points in the stack (points 3 and 2), leading to the removal of point 3 from the stack.
This adjustment allows for a left turn when point 4 is added atop point 2 in the stack.
The algorithm continues in this manner, examining each point in turn. Upon
completion, the stack holds all points forming the convex hull.
Task 1: Assignment Submission
Upload your solution to Task 1!
Input Formats
The test cases for each problem are present in the test_cases folder, and the
expected answers for each of these test cases are present in the
test_case_answers folder.
Part A
The input for 1A is the number of points, followed by each point.
Example
3 (Number of points we are constructing the hull for)
0 0 (Point 1)
5 6 (Point 2)
2 3 (Point 3)
Part B
The input for Part B is the same as Part A.
Part C
Add your answers to Part C as a pdf called written-tasks.pdf. Submit your
assignment using the "Mark" button. You may submit as many times as you
like.
Task 2: Baldur's Door
Baldur's Door is a new computer role-playing game based on the setting of a popular
table-top game called Delves & Drakes, the game features an extensive variety puzzles
and mechanics which critics have lauded as interesting and allowing for diverse modes
of play. The game's characters take on quests which lead to puzzles.
Part A
In the early quests of the game, the town's tavern is advertising exciting new flavours
for their soups. The cook has promised 500 silver pieces for each novel ingredient on
their list gathered. Though appearing generous for ingredient gathering in the nearby
forest, the party cleric noticed that each ingredient requires crawling between poison
bushes. The party rogue has the smallest build and will likely be able to crawl through
the bush without being scratched too badly - but will surely be afflicted. Once the
poison takes hold, each step taken will passively do a fixed amount of damage. The
cleric's healing spell can only be casted once the party rogue has exited the narrow
space. Since each casting of the healing spell requires expensive magical materials, you
will have to find the route that reaches the exit in the least possible steps.
An example of the forest pathways are shown below, where each edge represents a
step and each node represents a location the rogue can step to:
The forest layout above would be represented by the input to your program:
Where:
• the first line (8) is the number of locations the rogue can possibly step,
• the following line (11) is the number of connections between locations,
• the third line (0) is the location the rogue starts at,
• the fourth line (5) is the location the rogue exits the space and is in range to be
healed, and
• all following lines are pairs, indicating an undirected connection between the
two locations.
You may assume the list is sorted numerically by the first location and then (where the
first location is equal) by the second location. You may also assume locations are always
equal to or greater than 0 and numbered less than the number of locations.
The output should be the damage taken - assuming one point of damage is taken per
step.
Part B
After hearing the ease with which our protagonists were able to deal with the poison
forest, a local merchant staying at the tavern asks if the party would be interested in a
challenge. The merchant had come into possession of a number of lair maps that
showed the locations of all the traps in each lair. The merchant confessed they did not
have any non-mercantile skills but had managed to purchase information on how to
disarm each trap. After discussing the skills the party held, the merchant explained the
cost of the materials they'd need to disarm each trap they had the skills to disarm and
marked this total cost on each pathway. To preserve the most treasure, you'll need to
find the cheapest path through the lair.
Here is an example of one of these maps:
This map would be represented using the following format:
Which is the same as the format for Part A, but each edge specified includes an
additional third number describing the cost of disarming the trap. You may also assume
that all costs will be non-negative.
Part C
To reward the adventurers for their extensive help connecting the merchant with their
extensive treasures, they share their own prior connections. The documents they share
detail artisans who will offer ongoing services for a particular price - each artisan on the
map is able to create one material from another and reverse the process. Each
document is limited to the connections for a particular set of materials which are related
in some way. Since the general store merchants offer a new daily special periodically,
having a network which allows the creation of all materials from any material in the
documents will save a lot of money in future adventures. You will have to find the gold
you'll need to build the network which allows any material to be reached from any
other material in the document.
Here is an example of one of these documents:
This document would be represented using the following format:
Which is similar to the format for Part B, but excludes the fourth line that would
normally specify the final destination.
The output will be the minimum cost required to pay across all artisans such that each
material in the document can be made from any other material.
Part D
The final battle with Balgor, the Ruler of the Delve requires venturing into the
eponymous mythic delves. Mythic delves are typically reserved for the strongest of
adventurers, as each room applies a further unique condition which increases the
amount of damage done. Those who came before you have managed to map the
damage multiplier that each room applies, and have sold these precious maps to you
for a hefty sum. Since one of Balgor's minions lies at the end of each mythic delve, you
will have to reach the end of the delve with the lowest multiplier to have any chance of
besting them.
The game uses the mathematical floor of the calculated multiplier when calculating the
final damage multiplier (as this multiplier is displayed to the player as a whole number)
- however this is only applied to the final value, intermediate calculations retain the
fractional elements.
Here is an example of a map of a mythic delve:
This map would be given in the following format:
This is similar to the format of Part A and B, but the weight of each edge is the
percentage increase (e.g. a value of 20 implies a 20% increase in the damage taken in
each subsequent room). For this problem, successive rooms multiply by the weight of
the previous rooms, so in the above map, a path which takes the edge between 0 and
1, followed by the edge between 1 and 2, would apply a total increase of 32%.
The output should be the final percentage increase (without the percent sign) with any
fractional part of the percentage omitted.
Task 2: Assignment Submission
Upload your solution to Task 2!
Input Formats
The test cases for each problem are present in the test_cases folder (using
the format 2x-in-y.txt, where x is the part and y is the test case number)
and the expected answers for each of these test cases are present in the
same folder (using the format 2x-out-y.txt, where x is the part and y is the
test case number).
Part A
The details of the input to Part A are described in the previous slide:
8 (Number of lucations)
11 (Connections between locations)
0 (Start location)
5 (End location)
0 1 (Connection 1)
0 3 (Connection 2)
1 2 (Connection 3)
1 4 (Connection 4)
1 6 (Connection 5)
2 4 (Connection 6)
3 6 (Connection 7)
4 6 (Connection 8)
4 7 (Connection 9)
5 7 (Connection 10)
6 7 (Connection 11)
Part B
The details of the input to Part B are described in the previous slide:
8 (Number of lucations)
11 (Connections between locations)
0 (Start location)
5 (End location)
0 1 5 (Connection 1)
0 3 4 (Connection 2)
1 2 3 (Connection 3)
1 4 6 (Connection 4)
1 6 8 (Connection 5)
2 4 3 (Connection 6)
3 6 2 (Connection 7)
4 6 4 (Connection 8)
4 7 8 (Connection 9)
5 7 4 (Connection 10)
6 7 6 (Connection 11)
Part C
The details of the input to Part C are described in the previous slide:
8 (Number of lucations)
11 (Connections between locations)
0 (Start location)
0 1 5 (Connection 1)
0 3 4 (Connection 2)
1 2 3 (Connection 3)
1 4 6 (Connection 4)
1 6 8 (Connection 5)
2 4 3 (Connection 6)
3 6 2 (Connection 7)
4 6 4 (Connection 8)
4 7 8 (Connection 9)
5 7 4 (Connection 10)
6 7 6 (Connection 11)
Part D
The details of the input to Part D are described in the previous slide:
8 (Number of lucations)
10 (Connections between locations)
0 (Start location)
7 (End location)
0 1 20 (Connection 1 - +20%)
0 2 30 (Connection 2 - +30%)
1 2 10 (Connection 3 - +10%)
2 3 60 (Connection 4 - +60%)
3 4 80 (Connection 5 - +80%)
3 6 20 (Connection 6 - +20%)
4 5 20 (Connection 7 - +20%)
5 6 10 (Connection 8 - +10%)
5 7 90 (Connection 9 - +90%)
6 7 120 (Connection 10 - +120%)