Design a two-dimensional graph representing points, roads, and landmarks.

Each point has an identifier and two-dimensional coordinates. A road connects two points and can be traveled in either direction. The length of a road is the Euclidean distance between its endpoints.

The graph must support the following operations:

• Find the shortest travel distance between two points.
• Find the nearest reachable landmarks of a requested type, such as schools or hospitals.

Class

LandmarkGraph( List<String> points, List<String> roads, List<String> landmarks)

Parameters

• points: The points in the graph. Each entry is formatted as "pointId,x,y".
• roads: The bidirectional roads. Each entry is formatted as "firstPointId,secondPointId".
• landmarks: The landmarks stored at graph points. Each entry is formatted as "landmarkId,landmarkType,pointId".

Creates the graph with all its points, roads, and landmarks.

Method Signatures

Get the Shortest Distance

double getShortestDistance( String startPointId, String endPointId)

Parameters

• startPointId: The point where the journey begins.
• endPointId: The destination point.

Returns

The minimum total road distance from startPointId to endPointId.

Returns -1.0 when the destination cannot be reached.

Get the Nearest Landmarks

List<String> getNearestLandmarks( String pointId, String landmarkType, int limit)

Parameters

• pointId: The point from which distances are measured.
• landmarkType: The requested landmark type.
• limit: The maximum number of landmark identifiers to return.

Returns

Up to limit reachable landmark identifiers having the requested type.

Landmarks are ordered by their shortest road distance from pointId. When two landmarks have the same distance, the lexicographically smaller landmark identifier appears first.

Returns an empty list when no matching landmark is reachable.

Distance Rules

• For points at (x1, y1) and (x2, y2), the length of their road is sqrt((x2 - x1)² + (y2 - y1)²).
• A route may use only the roads supplied to the graph.
• A landmark's distance is the shortest road distance to the point containing that landmark.
• A landmark at the starting point has distance 0.0.

Constraints

• 1 ≤ points.size() ≤ 100,000
• 0 ≤ roads.size() ≤ 200,000
• 0 ≤ landmarks.size() ≤ 100,000
• 0 ≤ x, y ≤ 1,000,000
• Point identifiers and landmark identifiers are unique.
• Every identifier and landmark type contains between 1 and 30 letters, digits, underscores, or hyphens.
• Every road connects two different existing points.
• No two roads connect the same pair of points.
• Every landmark belongs to an existing point.
• 1 ≤ limit ≤ 100
• Answers within 10-5 of the correct distance are accepted.
• The input lists and method parameters are never null.

Examples

Example 1

LandmarkGraph( points = List.of( "A,0,0", "B,3,4", "C,6,8", "D,0,8"), roads = List.of( "A,B", "B,C", "A,D", "D,C"), landmarks = List.of( "centralSchool,school,B", "eastClinic,hospital,C", "riverHospital,hospital,D"))

getShortestDistance( startPointId = "A", endPointId = "C")

Returns 10.0.

The route from A through B to C has a total distance of 5.0 + 5.0 = 10.0.

getNearestLandmarks( pointId = "A", landmarkType = "hospital", limit = 2)

Returns List.of("riverHospital", "eastClinic").

The shortest distances are 8.0 to riverHospital and 10.0 to eastClinic.

Example 2

LandmarkGraph( points = List.of( "Center,5,0", "Left,0,0", "Right,10,0"), roads = List.of( "Center,Left", "Center,Right"), landmarks = List.of( "alphaSchool,school,Left", "betaSchool,school,Right"))

getNearestLandmarks( pointId = "Center", landmarkType = "school", limit = 1)

Returns List.of("alphaSchool").

Both schools are 5.0 units away, so the lexicographically smaller identifier is returned first.

Example 3

LandmarkGraph( points = List.of( "P,0,0", "Q,0,3", "R,10,0"), roads = List.of("P,Q"), landmarks = List.of( "nearbySchool,school,Q", "remoteHospital,hospital,R"))

getShortestDistance( startPointId = "P", endPointId = "R")

Returns -1.0.

getNearestLandmarks( pointId = "P", landmarkType = "hospital", limit = 3)

Returns List.of().

Point R is disconnected from point P, so its hospital is not reachable.