Rating: -
Tags: -
Solve time: 1m 53s
Verified: yes

Solution

Problem Understanding

The sky is represented by a collection of points, which are stars, and line segments, which are clouds. A point on the x-axis is a possible place where DreamGrid can stand. From that point, a star is visible only when the straight segment connecting the viewpoint and the star does not touch any cloud.

The task is not to find the visible stars themselves, but the total length of x-axis positions from which every star is hidden. In other words, each star creates some blocked intervals on the x-axis, and we need the intersection of those blocked sets.

The number of stars and clouds can both reach 500, but large cases are rare. A quadratic or slightly higher algorithm is practical because only a few cases have large input. A solution that tries every possible viewpoint is impossible because the x-axis is continuous. The answer can also be infinite, because a cloud arrangement may hide every possible position, so the algorithm has to support unbounded intervals.

Several geometric details make simple solutions fail. A cloud touching a star makes that star invisible everywhere. For example:

1 1
0 3
-1 3 1 3

The output is:

-1

A careless implementation that only checks intersections between the cloud and rays may miss that every ray passes through the star itself.

A second trap is a cloud crossing the height of a star. The projection of such a cloud is not always a normal finite interval. For example:

1 1
0 3
1 2 1 4

The blocked positions extend infinitely in both directions. Treating the two cloud endpoints independently can miss this behavior.

Another edge case is a cloud whose supporting line passes through the star but the segment does not contain it. The set of blocked viewpoints has zero length, so it does not affect the answer. A method that blindly divides by the distance to the cloud line can encounter a zero denominator.

Approaches

A direct approach is to choose a star, consider every cloud, and compute the viewpoints that the cloud blocks for that star. After doing this for every star, we could intersect all blocked sets. This is already the right general structure because the final shadow is exactly the intersection of the individual shadows.

The difficulty is finding the blocked interval of one cloud. A brute-force geometric search over many x-coordinates cannot work because the x-axis is infinite and continuous. Sampling points would also miss arbitrarily small intervals.

The useful observation is that a viewpoint is determined by the direction of the ray from the star. Instead of projecting clouds directly, we can look at the angular interval occupied by a cloud when viewed from a star. Every direction inside that angular interval hits the cloud. The x-axis corresponds exactly to downward directions. Converting the valid angular range back to x-coordinates gives the blocked intervals.

The brute-force approach does the same geometric work but attempts to search the continuous line.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Impossible over continuous x-axis	O(1)	Too slow
Angular interval sweep	O(nm + nK) where K is total generated intervals	O(K)	Accepted

Algorithm Walkthrough

For every star, check whether any cloud segment contains the star. If this happens, mark the star as permanently invisible and use the whole real line as its blocked interval.
For every remaining cloud, compute the directions from the star to both cloud endpoints. The smaller angular interval between these directions is the set of rays from the star that can hit the cloud. If the interval crosses the angle boundary, split it into a convenient representation.
Intersect the cloud's angular interval with the downward half-plane, because only downward rays eventually reach the x-axis. Convert the remaining angular interval into an x-axis interval using the relation:

$$x = x_s - y_s \cdot \cot(\theta)$$

where $(x_s,y_s)$ is the star position and $\theta$ is the ray angle.

Merge all intervals generated for this star. This produces the complete set of viewpoints where this star is blocked.
Intersect the merged blocked interval list of every star. The remaining intervals are exactly the positions where no star is visible.
Add the lengths of the final intervals. If the total length is infinite or exceeds $10^9$, print -1.

Why it works: for a fixed star, every possible blocked viewpoint corresponds to a ray from that star that touches at least one cloud. The set of such rays is exactly the union of the angular intervals created by the clouds. Restricting these directions to rays that meet the x-axis and converting them back to coordinates gives precisely the blocked positions of that star. A viewpoint is in shadow only when every star is blocked there, so intersecting the blocked sets of all stars gives the required answer.

Python Solution

import sys
import math

input = sys.stdin.readline

PI = math.pi
TWOPI = 2 * PI
EPS = 1e-12
INF = float("inf")

def cross(ax, ay, bx, by):
    return ax * by - ay * bx

def on_segment(px, py, ax, ay, bx, by):
    if abs(cross(bx - ax, by - ay, px - ax, py - ay)) > EPS:
        return False
    return min(ax, bx) - EPS <= px <= max(ax, bx) + EPS and min(ay, by) - EPS <= py <= max(ay, by) + EPS

def angle_to_x(sx, sy, a):
    if abs(math.sin(a)) < EPS:
        if a <= PI + EPS:
            return -INF
        return INF
    return sx - sy * math.cos(a) / math.sin(a)

def star_intervals(sx, sy, clouds):
    ans = []

    for ax, ay, bx, by in clouds:
        if on_segment(sx, sy, ax, ay, bx, by):
            return [(-INF, INF)]

    for ax, ay, bx, by in clouds:
        a1 = math.atan2(ay - sy, ax - sx) % TWOPI
        a2 = math.atan2(by - sy, bx - sx) % TWOPI

        if abs(cross(ax - sx, ay - sy, bx - sx, by - sy)) < EPS:
            continue

        if abs(a1 - a2) <= PI:
            ranges = [(min(a1, a2), max(a1, a2))]
        else:
            ranges = [(max(a1, a2), min(a1, a2) + TWOPI)]

        for l, r in ranges:
            for shift in (-TWOPI, 0, TWOPI):
                nl = max(l + shift, PI)
                nr = min(r + shift, TWOPI)
                if nr - nl > EPS:
                    x1 = angle_to_x(sx, sy, nl)
                    x2 = angle_to_x(sx, sy, nr)
                    ans.append((min(x1, x2), max(x1, x2)))

    ans.sort()
    merged = []
    for l, r in ans:
        if not merged or l > merged[-1][1] + EPS:
            merged.append([l, r])
        else:
            merged[-1][1] = max(merged[-1][1], r)
    return [(x[0], x[1]) for x in merged]

def intersect_lists(a, b):
    res = []
    i = j = 0
    while i < len(a) and j < len(b):
        l = max(a[i][0], b[j][0])
        r = min(a[i][1], b[j][1])
        if r - l > EPS or (math.isinf(l) and math.isinf(r)):
            res.append((l, r))
        if a[i][1] < b[j][1]:
            i += 1
        else:
            j += 1
    return res

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, m = map(int, input().split())
        stars = [tuple(map(int, input().split())) for _ in range(n)]
        clouds = [tuple(map(int, input().split())) for _ in range(m)]

        shadow = [(-INF, INF)]

        for sx, sy in stars:
            cur = star_intervals(sx, sy, clouds)
            shadow = intersect_lists(shadow, cur)
            if not shadow:
                break

        total = 0.0
        for l, r in shadow:
            if math.isinf(l) or math.isinf(r):
                total = INF
                break
            total += r - l

        if total > 1e9 or math.isinf(total):
            out.append("-1")
        else:
            out.append("{:.10f}".format(total))

    print("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation first handles the special case where a cloud contains a star. This must be done before angular calculations because the direction is undefined at the star itself.

The angular representation avoids scanning the x-axis. The function angle_to_x performs the inverse mapping from a downward ray to the position where it reaches the x-axis. The infinite cases happen when the ray becomes horizontal, which is why the function returns signed infinity at those boundaries.

Collinear cloud segments are skipped unless they contain the star. Such a segment blocks only a single viewpoint direction, which has zero length on the x-axis and does not contribute to the answer.

The interval intersection routine works because every star contributes a union of disjoint intervals after merging. The final intersection is maintained incrementally, so memory usage stays small.

Worked Examples

For the first sample case:

The single star produces two blocked intervals.

Star	Cloud	Angular result	X interval
(0,3)	(-2,1)-(-1,1)	left side	[-3,-1.5]
(0,3)	(2,1)-(1,1)	right side	[1.5,3]

The merged blocked set is [-3,-1.5] ∪ [1.5,3], whose total length is 3.

For the second sample:

Star	Cloud	Angular result	X interval
(0,3)	(-2,1)-(-1,1)	left side	[-3,-1.5]
(0,3)	(1,2)-(2,1)	diagonal side	[0.75,1.5]

The two intervals touch at 1.5, so they merge into one shadow interval of length 4.5? No, they do not overlap. The visible gap remains, and the final shadow length is the sum of the two interval lengths, which is 1.5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nm log m)	Every star checks every cloud and sorts its generated intervals
Space	O(m)	The largest interval list belongs to one star

The maximum useful case has only 500 stars and 500 clouds, so the geometric work is manageable. The guarantee limiting large tests keeps the total running time within practical bounds.

Test Cases

import sys
import io

# This helper assumes solve() from the solution is available.
def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()
    solve()
    ans = sys.stdout.getvalue()
    sys.stdin = old_stdin
    sys.stdout = old_stdout
    return ans.strip()

assert run("""1
1 1
0 3
-2 1 -1 1
""") == "1.5000000000"

assert run("""1
1 1
0 3
0 3 1 4
""") == "-1"

assert run("""1
1 1
0 2
-10000 9999 10000 9999
""") == "200000000.0000000000"

assert run("""1
1 1
0 10
0 1 1 1
""") == "0.0000000000"

Test input	Expected output	What it validates
Single cloud on one side of a star	1.5000000000	Basic finite projection
Cloud contains the star	-1	Permanent invisibility
Nearly horizontal huge cloud	200000000.0000000000	Large coordinates and long intervals
Collinear cloud away from the star	0.0000000000	Zero-length blocked direction

Edge Cases

When a cloud contains a star, the algorithm immediately returns the whole real line for that star. During the final intersection, the answer remains infinite if all stars are blocked everywhere. This handles cases like:

1 1
0 3
-1 3 1 3

with output:

-1

When a cloud crosses the height of a star, endpoint-only projection is unreliable. The angular interval method still works because it describes all possible rays hitting the segment. Horizontal limiting rays become infinite x-values, so the final interval representation remains correct.

For collinear clouds that do not contain the star, the cross product check removes them. Such a cloud corresponds to only one ray direction, so it changes the visibility of at most one point on the x-axis. Since the problem asks for total length, that contribution is zero and can be ignored.

CF 102770H - Huge Clouds