Day3C-Hills

3日目
Problem C : Hills
担当:稲葉 & 野田
講評担当:野田
問題(1)


複数の線分が与えられる
三角形の数を数えてください

三本の線分に囲まれていて、他の線分が侵入
していない領域だけが三角形です。
問題(2)

線分の端点が他の線分上に来ない


線分同士は交差するor離れている
3本以上の線分一点で重なることは無い
準備

O(n4)はもちろんTLE


O(n2ちょっと)
交差判定＆交点計算

ライブラリ
解法



二重ループで全交点を列挙する
交点を点、それらの間の線分を枝として
グラフ(隣接リスト)を作成する
各枝に隣接する点の共通隣接点を調べる
その他

分数vs浮動小数

分数Ver(野田)・・・350行

分数ライブラリだけで100行


問題作成時3本以上の線分が一点で重なっても良いとさ
れていたため、その対処として分数を使用した
浮動小数Ver(稲葉)・・・120行
結果





Submitチーム数・・・４
総Submit数・・・8
Accept・・・?
最速Submit・・・()
最速Accept・・・()
終わりに
//Hills
//解答作成者 : 野田
//解法 : 全ての線について交点を求め隣り合う交
点を枝で結んだグラフを作成する
//
各枝に隣接する点のペアについて、それら
のペアの隣接する点の集合の積を求める
//寸感 : もうコード見たくない
#include <iostream>
終了

御清聴有難うございました

Download Report