Half Plane Painting
Source: aizu

Half Plane Painting
Problem Statement

You have a 2D plane that is initially entirely white. You can perform the following operation any number of times:

Choose a line and the half-plane bounded by this line. Then, perform one of the following actions:
Paint the half-plane (excluding the boundary) black.
Paint the half-plane and the boundary white.

You are given the polygon $P$ with $N$ vertices, which is not necessarily convex. The vertices of $P$ are given in counterclockwise order as $(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)$, and the $i$-th edge of $P$ connects vertex $(x_i, y_i)$ to vertex $(x_{(i\mod N)+1}, y_{(i\mod N)+1})$.

Determine whether it is possible to use the aforementioned operations to paint only the interior of polygon $P$black, leaving everything else white.

Input

The input is given in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

$3 \leq N \leq 4,000$
$-10^7 \leq x_i, y_i \leq 10^7 (1 \leq i \leq N)$
$(x_i, y_i) \ne (x_j, y_j) (i \ne j)$
The vertices of polygon $P$ are given in counterclockwise order.
The edges of polygon $P$ do not share any points other than the vertices.
Each internal angle of polygon $P$ is not $180$ degrees.
All input values are integers.
Output

If it is possible to achieve the desired state with the operations, output Yes; otherwise, output No.

Sample Input 1
4
10 -5
2 -5
-7 6
-7 -8

Sample Output 1
Yes

Sample Input 2
12
17 1
19 3
12 10
19 17
17 19
10 12
3 19
1 17
8 10
1 3
3 1
10 8

Sample Output 2
No


C++ solution:
// AOJ #3630 Half Plane Painting
// 2025.4.26

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define gc() getchar_unlocked()

int Cin() {
    int n = 0; int c = gc();
    if (c == '-') { c = gc();
        do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
        return -n;
    }
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

const int MAXN = 4000;
struct P { ll x, y; };
bitset<MAXN> bitL[MAXN], bitR[MAXN];
int cntL[MAXN], cntR[MAXN];
bool used[MAXN], inq[MAXN];
int q[MAXN];

int main(){
    int N = Cin();
    vector<P> p(N);
    for(int i = 0; i < N; i++) p[i].x = Cin(), p[i].y = Cin();

    for(int k = 0; k < N; k++){
        auto &A = p[k];
        auto &B = p[(k+1)%N];
        for(int e = 0; e < N; e++){
            if(e == k) continue;
            auto &C = p[e];
            auto &D = p[(e+1)%N];
            ll c1 = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
            ll c2 = (B.x - A.x) * (D.y - A.y) - (B.y - A.y) * (D.x - A.x);
            if(c1 < 0 || c2 < 0) bitL[k].set(e);
            if(c1 > 0 || c2 > 0) bitR[k].set(e);
        }
        cntL[k] = bitL[k].count();
        cntR[k] = bitR[k].count();
    }

    int ql = 0, qr = 0, sel = 0;
    for(int i = 0; i < N; i++){
        if(cntL[i] == 0 || cntR[i] == 0){
            q[qr++] = i;
            inq[i] = true;
        }
    }

    while(ql < qr){
        int e = q[ql++];
        inq[e] = false;
        if(used[e]) continue;
        used[e] = true;
        sel++;
        for(int k = 0; k < N; k++){
            if(used[k]) continue;
            if(bitL[k].test(e)){
                bitL[k].reset(e);
                if(--cntL[k] == 0 && !inq[k]){
                    q[qr++] = k;
                    inq[k] = true;
                }
            }
            if(bitR[k].test(e)){
                bitR[k].reset(e);
                if(--cntR[k] == 0 && !inq[k]){
                    q[qr++] = k;
                    inq[k] = true;
                }
            }
        }
    }
    cout << (sel == N ? "Yes" : "No") << endl;
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Point struct {
	x, y int64
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	// Read N
	scanner.Scan()
	N, _ := strconv.Atoi(scanner.Text())

	p := make([]Point, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		x, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		scanner.Scan()
		y, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		p[i] = Point{x, y}
	}

	bitL := make([]uint64, N)
	bitR := make([]uint64, N)
	cntL := make([]int, N)
	cntR := make([]int, N)
	used := make([]bool, N)
	inq := make([]bool, N)
	q := make([]int, 0, N)

	for k := 0; k < N; k++ {
		A := p[k]
		B := p[(k+1)%N]
		for e := 0; e < N; e++ {
			if e == k {
				continue
			}
			C := p[e]
			D := p[(e+1)%N]
			c1 := (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x)
			c2 := (B.x-A.x)*(D.y-A.y) - (B.y-A.y)*(D.x-A.x)
			if c1 < 0 || c2 < 0 {
				bitL[k] |= 1 << uint(e)
				cntL[k]++
			}
			if c1 > 0 || c2 > 0 {
				bitR[k] |= 1 << uint(e)
				cntR[k]++
			}
		}
	}

	for i := 0; i < N; i++ {
		if cntL[i] == 0 || cntR[i] == 0 {
			q = append(q, i)
			inq[i] = true
		}
	}

	sel := 0
	for len(q) > 0 {
		e := q[0]
		q = q[1:]
		inq[e] = false
		if used[e] {
			continue
		}
		used[e] = true
		sel++
		for k := 0; k < N; k++ {
			if used[k] {
				continue
			}
			if (bitL[k]>>uint(e))&1 != 0 {
				bitL[k] &^= 1 << uint(e)
				cntL[k]--
				if cntL[k] == 0 && !inq[k] {
					q = append(q, k)
					inq[k] = true
				}
			}
			if (bitR[k]>>uint(e))&1 != 0 {
				bitR[k] &^= 1 << uint(e)
				cntR[k]--
				if cntR[k] == 0 && !inq[k] {
					q = append(q, k)
					inq[k] = true
				}
			}
		}
	}

	if sel == N {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static class Point {
        long x, y;
        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Point[] p = new Point[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            p[i] = new Point(x, y);
        }

        BitSet[] bitL = new BitSet[N];
        BitSet[] bitR = new BitSet[N];
        int[] cntL = new int[N];
        int[] cntR = new int[N];
        boolean[] used = new boolean[N];
        boolean[] inq = new boolean[N];
        int[] q = new int[N];
        int ql = 0, qr = 0;

        for (int k = 0; k < N; k++) {
            Point A = p[k];
            Point B = p[(k + 1) % N];
            bitL[k] = new BitSet(N);
            bitR[k] = new BitSet(N);
            for (int e = 0; e < N; e++) {
                if (e == k) continue;
                Point C = p[e];
                Point D = p[(e + 1) % N];
                long c1 = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
                long c2 = (B.x - A.x) * (D.y - A.y) - (B.y - A.y) * (D.x - A.x);
                if (c1 < 0 || c2 < 0) {
                    bitL[k].set(e);
                }
                if (c1 > 0 || c2 > 0) {
                    bitR[k].set(e);
                }
            }
            cntL[k] = bitL[k].cardinality();
            cntR[k] = bitR[k].cardinality();
            if (cntL[k] == 0 || cntR[k] == 0) {
                q[qr++] = k;
                inq[k] = true;
            }
        }

        int sel = 0;
        while (ql < qr) {
            int e = q[ql++];
            inq[e] = false;
            if (used[e]) continue;
            used[e] = true;
            sel++;
            for (int k = 0; k < N; k++) {
                if (used[k]) continue;
                if (bitL[k].get(e)) {
                    bitL[k].clear(e);
                    int newCnt = bitL[k].cardinality();
                    if (newCnt == 0 && !inq[k]) {
                        q[qr++] = k;
                        inq[k] = true;
                    }
                    cntL[k] = newCnt;
                }
                if (bitR[k].get(e)) {
                    bitR[k].clear(e);
                    int newCnt = bitR[k].cardinality();
                    if (newCnt == 0 && !inq[k]) {
                        q[qr++] = k;
                        inq[k] = true;
                    }
                    cntR[k] = newCnt;
                }
            }
        }
        System.out.println(sel == N ? "Yes" : "No");
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N;
let vertices = [];
let bitL = [];
let bitR = [];
let cntL = [];
let cntR = [];
let used = [];
let inq = [];
let q = [];

function main() {
    rl.on('line', (line) => {
        if (N === undefined) {
            N = parseInt(line.trim());
        } else {
            const [x, y] = line.trim().split(' ').map(Number);
            vertices.push({ x, y });
            if (vertices.length === N) {
                solve();
                rl.close();
            }
        }
    });
}

function solve() {
    // Initialize bitL and bitR as arrays of arrays (simulated with arrays of booleans)
    bitL = new Array(N);
    bitR = new Array(N);
    cntL = new Array(N).fill(0);
    cntR = new Array(N).fill(0);
    used = new Array(N).fill(false);
    inq = new Array(N).fill(false);
    q = new Array(N).fill(0);

    for (let k = 0; k < N; k++) {
        bitL[k] = new Array(N).fill(false);
        bitR[k] = new Array(N).fill(false);
    }

    for (let k = 0; k < N; k++) {
        const A = vertices[k];
        const B = vertices[(k + 1) % N];
        for (let e = 0; e < N; e++) {
            if (e === k) continue;
            const C = vertices[e];
            const D = vertices[(e + 1) % N];
            const c1 = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
            const c2 = (B.x - A.x) * (D.y - A.y) - (B.y - A.y) * (D.x - A.x);
            if (c1 < 0 || c2 < 0) {
                bitL[k][e] = true;
                cntL[k]++;
            }
            if (c1 > 0 || c2 > 0) {
                bitR[k][e] = true;
                cntR[k]++;
            }
        }
    }

    let ql = 0, qr = 0, sel = 0;
    for (let i = 0; i < N; i++) {
        if (cntL[i] === 0 || cntR[i] === 0) {
            q[qr++] = i;
            inq[i] = true;
        }
    }

    while (ql < qr) {
        const e = q[ql++];
        inq[e] = false;
        if (used[e]) continue;
        used[e] = true;
        sel++;
        for (let k = 0; k < N; k++) {
            if (used[k]) continue;
            if (bitL[k][e]) {
                bitL[k][e] = false;
                cntL[k]--;
                if (cntL[k] === 0 && !inq[k]) {
                    q[qr++] = k;
                    inq[k] = true;
                }
            }
            if (bitR[k][e]) {
                bitR[k][e] = false;
                cntR[k]--;
                if (cntR[k] === 0 && !inq[k]) {
                    q[qr++] = k;
                    inq[k] = true;
                }
            }
        }
    }

    console.log(sel === N ? "Yes" : "No");
}

main();

Python solution:
import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    p = []
    for _ in range(N):
        x = int(input[ptr])
        y = int(input[ptr + 1])
        p.append((x, y))
        ptr += 2

    # Initialize bitmasks for left and right sides
    bitL = [0] * N
    bitR = [0] * N
    cntL = [0] * N
    cntR = [0] * N

    for k in range(N):
        A = p[k]
        B = p[(k + 1) % N]
        # Line AB: (B.x - A.x, B.y - A.y)
        # For each edge e (C, D), check if C and D are on the left or right of AB
        for e in range(N):
            if e == k:
                continue
            C = p[e]
            D = p[(e + 1) % N]
            # Cross product (B - A) x (C - A)
            c1 = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
            # Cross product (B - A) x (D - A)
            c2 = (B[0] - A[0]) * (D[1] - A[1]) - (B[1] - A[1]) * (D[0] - A[0])
            if c1 < 0 or c2 < 0:
                bitL[k] |= 1 << e
                cntL[k] += 1
            if c1 > 0 or c2 > 0:
                bitR[k] |= 1 << e
                cntR[k] += 1

    used = [False] * N
    inq = [False] * N
    q = []
    for i in range(N):
        if cntL[i] == 0 or cntR[i] == 0:
            q.append(i)
            inq[i] = True

    sel = 0
    while q:
        e = q.pop(0)
        inq[e] = False
        if used[e]:
            continue
        used[e] = True
        sel += 1
        for k in range(N):
            if used[k]:
                continue
            # Check if e is in bitL[k]
            if (bitL[k] >> e) & 1:
                bitL[k] ^= 1 << e
                cntL[k] -= 1
                if cntL[k] == 0 and not inq[k]:
                    q.append(k)
                    inq[k] = True
            # Check if e is in bitR[k]
            if (bitR[k] >> e) & 1:
                bitR[k] ^= 1 << e
                cntR[k] -= 1
                if cntR[k] == 0 and not inq[k]:
                    q.append(k)
                    inq[k] = True

    print("Yes" if sel == N else "No")

if __name__ == "__main__":
    main()

Ruby solution:
def main
  # Read input
  n = gets.to_i
  points = []
  n.times do
    x, y = gets.split.map(&:to_i)
    points << [x, y]
  end

  # Initialize data structures
  left_deps = Array.new(n) { [] }
  right_deps = Array.new(n) { [] }
  left_count = Array.new(n, 0)
  right_count = Array.new(n, 0)

  # Compute dependencies between edges
  n.times do |i|
    a = points[i]
    b = points[(i + 1) % n]
    
    n.times do |j|
      next if i == j

      c = points[j]
      d = points[(j + 1) % n]

      # Compute cross products
      cross1 = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
      cross2 = (b[0] - a[0]) * (d[1] - a[1]) - (b[1] - a[1]) * (d[0] - a[0])

      # Determine dependencies
      if cross1 < 0 || cross2 < 0
        left_deps[i] << j
      end
      if cross1 > 0 || cross2 > 0
        right_deps[i] << j
      end
    end

    left_count[i] = left_deps[i].size
    right_count[i] = right_deps[i].size
  end

  # Initialize processing queue
  processed = Array.new(n, false)
  in_queue = Array.new(n, false)
  queue = []

  # Seed queue with edges that have no dependencies
  n.times do |i|
    if left_count[i] == 0 || right_count[i] == 0
      queue << i
      in_queue[i] = true
    end
  end

  processed_count = 0

  # Process edges in queue
  while !queue.empty?
    current = queue.shift
    in_queue[current] = false
    next if processed[current]

    processed[current] = true
    processed_count += 1

    # Update dependencies for other edges
    n.times do |j|
      next if processed[j]

      # Check left dependencies
      if left_deps[j].include?(current)
        left_deps[j].delete(current)
        left_count[j] -= 1
        if left_count[j] == 0 && !in_queue[j]
          queue << j
          in_queue[j] = true
        end
      end

      # Check right dependencies
      if right_deps[j].include?(current)
        right_deps[j].delete(current)
        right_count[j] -= 1
        if right_count[j] == 0 && !in_queue[j]
          queue << j
          in_queue[j] = true
        end
      end
    end
  end

  # Output result
  puts processed_count == n ? "Yes" : "No"
end

main