Nova 如何来实现呢

Question

Problem Description
The Lich is a powerful hero that he can kill a wisp with his skill Frost Nova. The Burning Legion wants to conquer the forest so they sent some liches to kill all the wisps. A lich can kill a wisp once he could see the wisp and the wisp in his attack range. So the lich can attack a wisp when the distance between them is less than or equal to specific R and no trees are on the segment between the lich and wisp. Each lich has a cool down time that once he used Frost Nova he has to wait a few seconds for the next attack. Different liches may have different attack range and cool down time. The Lich King is the leader of the Burning Legion and he wants to arrange the attack order so the liches can wipe out all the wisps as soon as possible.

Input
The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, M, K, indicating the number of lich, the number of wisps and the number of trees. The next N lines, each line consists of four integers x, y, r, t indicating the coordinate of that a lich, the radius of the attack range that lich’s Frost Nova can reach and the value of cool down time. The next M lines, each line consists of two integers x, y indicating the coordinate of each wisp. The last K lines, each line consists of three integers x, y, r, indicating the coordinate and radius of a tree. A lich cannot attack a wisp if the segment between them has a common point with the tree. The lich, wisp and trees will not overlap with each other.

Output
Output the minimum time lich need to kill all the wisps on a single line, or -1 if lich cannot kill all the wisps.

Constrains
0 < T <= 20
0 <= N, M, K <= 200
-10000 <= x, y <= 10000
0 <= r, t <= 10002

Sample Input
1
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output
5

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

To solve this problem, we can use a greedy algorithm approach. First, we can create a function to calculate the distance between two points (lich and wisp). We can also create a function to check if there is any tree on the segment between two points. Next, we can iterate through all possible combinations of lich and wisp pairs, and calculate the time needed for each lich to kill all the wisps. We can then choose the minimum time needed among all liches. If a lich cannot kill all the wisps, we can return -1. Below is a sample code to solve this problem:

import math
def calculate_distance(x1, y1, x2, y2):
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
def has_tree_on_segment(x1, y1, x2, y2, trees):
    for tree in trees:
        x, y, r = tree
        if (x1 <= x <= x2 or x2 <= x <= x1) and (y1 <= y <= y2 or y2 <= y <= y1):
            if (x - x1) * (y2 - y1) == (y - y1) * (x2 - x1) and calculate_distance(x1, y1, x, y) < calculate_distance(x1, y1, x2, y2):
                return True
    return False
def min_time_to_kill_all_wisps(N, M, K, liches, wisps, trees):
    min_time = float('inf')
    
    for lich in liches:
        time = 0
        for wisp in wisps:
            distance = calculate_distance(lich[0], lich[1], wisp[0], wisp[1])
            if distance <= lich[2] and not has_tree_on_segment(lich[0], lich[1], wisp[0], wisp[1], trees):
                time = max(time, distance + lich[3])
            else:
                time = float('inf')
                break
        min_time = min(min_time, time)
    
    return min_time if min_time != float('inf') else -1
# Sample Input
T = int(input())
for _ in range(T):
    N, M, K = map(int, input().split())
    liches = [list(map(int, input().split())) for _ in range(N)]
    wisps = [list(map(int, input().split())) for _ in range(M)]
    trees = [list(map(int, input().split())) for _ in range(K)]
    
    print(min_time_to_kill_all_wisps(N, M, K, liches, wisps, trees))

You can test this code with the sample input provided in the problem description.