Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1853-e85dfa32
この記事にトラックバックする(FC2ブログユーザー)

UVa 11930 - Rectangles (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11930

問題概要

2次元平面上の長方形がN個 (1000以下) 与えられる.
それぞれの長方形から対角線を1つ選んで,選んだ対角線がすべて交わらないようにできるかどうかを判定する問題.
交わるとは,共通点を1点以上持つこと.

解法

それぞれの対角線が交わるかどうかを判定して2-SATに落として,強連結成分分解して解く.
長方形の頂点の座標が時計回りや反時計回りに与えられてるとは限らない点に注意.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1853-e85dfa32
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。