Segments, polygons and hulls

Questions 1 to 5 of 8

1. 1. A teammate's segment test returns NO for the segments (0, 0)-(4, 0) and (2, 0)-(2, 3), which touch at (2, 0). The test is: orient(a, b, c) * orient(a, b, d) < 0 and orient(c, d, a) * orient(c, d, b) < 0. What is wrong?

   The cross product uses the wrong sign, so every answer is flippedThe test only accepts proper crossings. A touch at an endpoint makes one orientation zero, so the product is not negative. It needs the bounding box check for touching and collinear casesFloating point rounds the touch point away, so the test cannot see itThe test is right, because touching segments are never intersections in contest problems
2. 2. What is the doubled area (the shoelace sum) of the square with corners (0, 0), (4, 0), (4, 4) and (0, 4), listed in that order? Give the integer.

   Type a number.

3. 3. Which statements about the shoelace formula for a simple polygon with integer corners are true?

   Pick every answer that is true.

   Reversing the order of the corners flips the sign of the sumThe doubled area is always evenDividing the sum by 2 keeps an integer, so the area can be printed as a long longA positive sum means the corners run counterclockwise
4. 4. Judge data puts query points on vertices and on walls. Which order of tests gives the right answer for a point on a wall?

   Count ray crossings first. If the count is odd, answer INSIDE. Check the boundary lastUse a double division for each crossing x, then compare it with 0.5Check the boundary first, using cross product zero and a bounding box for each edge. Then use the ray test for the other pointsSkip the boundary check, because random tests almost never hit an edge
5. 5. An AI tool wrote this check for whether a query point p lies on the wall from a to b: ``cpp bool on_wall(P p, P a, P b) { return cross(a, b, p) == 0; } `` What does it get wrong?

   It reports a point on the same line past the wall's ends as on the wall. For the wall (0, 0) to (2, 2), the point (5, 5) gives 0 and is wrongly reported as on the wallIt uses double, so the cross product rounds and the result is randomIt returns true for every point when the wall is listed clockwiseNothing, the check is complete, because a zero cross product always means the point is on the wall