2017-11

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

実践的プログラミング 2011/06/06

POJ 1375: Intervals


平面上に,点光源と N 個の円が与えられる.円は光源より下にある.y = 0 上にできる影を互いに交わらない区間の和集合として出力する.
N <= 500.

円に点から引いた接点,直線と直線の交点でそれぞれの影は求める.pair でソートして,1 つだけ現在作りかけの区間を持ちつつなめていく (右端を max していく,離れたら出力).

右端を単に書き換えていて,影が別の影に含まれる場合に落ちていた.

霊体物質化能力


N 体の幽霊がいて,それぞれは n[i] 角形.ある点に人がいて,人から距離 r 以内の幽霊は実体化される.2 体の実体化された幽霊が共有点を持つ場合,それらは衝突し,衝突した幽霊の組のうち面積が最大でないものがやられる.r が 0 から連続的に増えていくとき,最初に衝突が起こるときにおける,消える幽霊をすべて出力する.
N <= 100,n[i] <= 20.

点と多角形の距離および,多角形と多角形が共有点を持つかを判定する.前者は点が内部に含まれているならば 0,そうでないならば各辺との距離を調べて O(n[i]).後者は一方の 1 頂点が他方に含まれているならば YES,そうでないならば各辺の組を調べて O(n[i]n[j]).
準備ができたら,距離が近い多角形から順に加えて衝突するかを見て,最初の衝突があったら r が同じ値である限り範囲を伸ばし,衝突するものを併合して連結成分での面積の最大値を調べる.

衝突しないものまで併合してしまった.また,人が幽霊に含まれるケースを忘れていた.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/12-715d81ee

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。