← CSES Better

Fencing the Herd

USACO · 2015 · February · gold-3

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

geometry · convex-hull · data-structures

The organizer’s problem statement is available at the official source link.

sample trace

Fencing the Herd: test line separation dynamically

For each query, a fence is usable only when all current cows lie strictly on one side. The sample changes the point set between tests.

initial Points

00
01
10

events

  • type
    query
    line
    223
    answer
    YES
  • type
    insert
    point
    11
  • type
    query
    line
    223
    answer
    NO
  • type
    query
    line
    011
    answer
    NO

output

YESNONO
  1. 1

    Evaluate a fence

    Use the sign of Ax+By-C for each cow: mixed signs or a zero means the fence is unusable.
  2. 2

    Insert the new cow

    The first query is YES; after adding (1,1), the same line has points on both sides and becomes NO.
  3. 3

    Check boundary points

    The final line y=1 passes through existing cows, so it is also NO. The editorial accelerates these dynamic side queries with convex-hull structures.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.