[問題案] Halfplane Intersection

[SSRS-cp]

問題名: Halfplane Intersection

問題

$N$ 個の半平面 $a_ix+b_iy \leq c_i$ が与えられる。それらの共通部分を出力せよ？

制約

要調整

入力

N a_0 b_0 c_0 a_1 b_1 c_1 ... a_{N-1} b_{N-1} c_{N-1}

出力

要検討

メモ

Twitter でいろいろ議論があったので立てておきますが、出力形式などの議論が必要です

[maspypy]

• 不等式の等号の有無について

有限個の集合について、「内部の交わり」「交わりの内部」は等しいので、$\leq$ の場合が解ければ $<$ も解けている。 ので、$\leq$ だけあれば十分だと思います。 （$\leq, <$ が混在する場合：出題例に心当たりがある人がいなければ、そこまでやらないことにした方が良いと思う）

[maspypy]

https://twitter.com/noshi91/status/1555482168050466816?s=20&t=-t4pjLcJs8KrZr50IJz2WQ

・次元 2 　・平面全体 　・半平面 　・帯 　・その他の非有界 　・有界 ・次元 1 　・直線 　・半直線 　・線分 ・次元 0 ・空

[maspypy]

誰か意欲的な人が、これでどうでしょうという提案をひとつ作らない限り、ずっと放置されそうな気がする…。

[demidenko]

output suggestion: for each unique point of result print pair of ids of half-planes that form it

[SSRS-cp]

output suggestion: for each unique point of result print pair of ids of half-planes that form it

What should we output if the input halfplanes are x>=0 and x<=1 ?

[demidenko]

output suggestion: for each unique point of result print pair of ids of half-planes that form it

What should we output if the input halfplanes are x>=0 and x<=1 ?

if we want more, we can print each unique edge: is it segment, line, or ray. but again, for tests {x>=0} and {x>=0, x<=0} answer again equals.

what if add some "clockwise" thinking?..

[SSRS-cp]

Currently we are thinking of first printing the type of the shape of intersection (there are 10 types, 9 if the case of no halfplanes is excluded) and print the ids of the halfplanes that form its edges in order. There will be some tricky edge cases though

[maspypy]

とりあえず考えられる出力方法をひとつ置いておきます。

• 半平面 これは、下記の「その他非有界」（UNBOUNDEDPOLYGON）の特殊ケースなので無し

• 帯 $c_0 \leq ax+by \leq c_1$

STRIP
a b c_0 c_1

• その他の非有界

UNBOUNDEDPOLYGON
N
a_0 b_0 c_0
:
a_{N-1} b_{N-1} c_{N-1}

$N=1$ とした場合が半平面

• 有界

BOUNDEDPOLYGON
N
a_0 b_0 c_0
:
a_{N-1} b_{N-1} c_{N-1}

• 直線 $ax + by = c$

LINE
a b c

• 半直線 from $(a_1/b_1,c_1/d_1)$, direction $\overrightarrow{d} = (d_x, d_y)$

HALFLINE
a_1 b_1 c_1 d_1
d_x d_y

• 線分 between $(a_1/b_1,c_1/d_1)$ and $(a_2/b_2,c_2/d_2)$

SEGMENT
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2

・次元 0 $(a/b,c/d)$

POINT
a b c d

・空

EMPTY

[SSRS-cp]

「その他の非有界」には半平面 3 個以上で構成される場合もありそうです (x≧0, y≧0, x+y≧1 など)

[maspypy]

なおした。境界の線分を並べる形でいいのかな。

[SSRS-cp]

境界となる半平面の番号を出力という形式も考えられます

利点: 半直線・線分・点のときに分数出力が不要

[SSRS-cp]

https://twitter.com/akakimidori/status/1555507960948080640

[maspypy]

例えば 1 点がのこるときにどの半平面の集合を選ぶかとかがややこしいという話だと思っていたので、とりあえずこのようにしました。とりあえず案1ということで。

[tatyam-prime]

案

答えと境界が共通部分を持つような半平面を全て、反時計回りに出力 (反時計回りであればなんでもよい)

m
a_1 b_1 c_1
:
a_m b_m c_m

制約

• $\gcd(a_i, b_i, c_i) = 1$
• 半平面は pairwise distinct

[noshi91]

答えの頂点を掠めるような半平面が出力に入っているのは嬉しいのか嬉しくないのかという問題はある。凸包で辺上の点を含めるかと近い問題で、Convex Layers では含めていて Incremental Convex Hull では未定？

[noshi91]

https://twitter.com/noimi_kyopro/status/1555482085397131264

のいみ @noimi_kyopro まあでも正直本当の実用上だと 大きさ 2 × 10^9 の bounding box で囲んで困ることないしそれして有界の場合に限ってもいい気はするけどね

参考