← 返回题目列表

AtCoder · joisc2012_constellation

constellation. 星座

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

星座 - 原题 PDF 第 1 页
原题PDF第4页
星座 - 原题 PDF 第 2 页
原题PDF第5页
星座 - 原题 PDF 第 3 页
原题PDF第6页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                      Contest Day 2 – Constellation

                          星座(Constellation)



  JOI 君は星空の観察が大好きな少年である.毎晩のように星空を観察しては,それぞれの星がどの星座
に属するのかを調べて楽しんでいる.
 ある晩,JOI 君がいつものように星空を観察していると,見たことのない星をN 個発見した.これらの
星がどの星座に属するのかが気になったJOI 君は,夜空を写真に撮り,翌日図書館でこれらの星について
調べてみた.すると,これらの星はすべて星座A か星座B のどちらかに属することと,これらの星のうち
いくつかの星がどちらに属しているかがわかった.だが,その他の星については,どちらの星座に属して
いるかがわからなかった.JOI 君は,星座A と星座B を構成する星の集合として考えられるものが何通り
あるかが気になった.なお,星の大きさは十分小さいので,点とみなしてよい.
 ただし,星座とは,写真上で1 つ以上の星と,星2 つを結ぶ線分いくつかからなり,以下の条件を満た
す.星1 つのみからなるものも星座とみなすことに注意せよ.

   • ある星座を構成する任意の2 つの星は,写真上でその星座を構成する線分を辿ることで互いに到達す
   ることができる.

   • ある星座を構成する線分と別の星座を構成する線分は交わらない.
 また,JOI 君の発見した星は,以下の条件を満たす.

   • どの3 つの星も,写真上で同一直線上にない.
   • どの星も星座A または星座B に属し,JOI 君の発見した星以外で星座A または星座B に属するもの
   は存在しない.


課題

 N 個の星の情報が与えられたとき,星座A と星座B を構成する星の集合として考えられるものの総数を
1 000 000 007 (= 109 + 7) で割った余りを求めるプログラムを作成せよ.


制限

   2 ≦N ≦100 000          JOI 君の発見した星の数
   0 ≦Xi ≦109, 0 ≦Yi ≦109  星i の写真上での座標


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N が書かれており,JOI 君の発見した星の数を表す.


                         星座– 1 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                      Contest Day 2 – Constellation

   • 続くN 行には,星の情報が書かれている.i + 1 行目(1 ≦i ≦N) には,3 つの整数Xi, Yi,Ci が空白区
   切りで書かれている.Xi, Yi は星i の写真上での座標が(Xi, Yi) であることを表す.Ci は星i が星座A
   と星座B のどちらに属しているかを表す.

       –  Ci = 0 の場合は星i がどちらの星座に属するかわからないことを表す.
       –  Ci = 1 の場合は星i が星座A に属していることを表す.
       –  Ci = 2 の場合は星i が星座B に属していることを表す.


出力

 星座A と星座B を構成する星の集合として考えられるものの総数を1 000 000 007 (= 109 + 7) で割った余
りを1 行で出力せよ.そのような星の集合が存在しない場合,0 を出力せよ.


採点基準

 採点用データのうち,配点の10%分についてはN ≦10 を満たす.
 採点用データのうち,配点の50%分についてはN ≦300 を満たす.


入出力例

  入力例1        出力例1
   4                    2
   1 1 1
   2 1 1
   1 2 0
   2 2 2

 この入力例は,次の図に対応している.ただし,黒い点は星座A に属する星を,白い点は星座B に属す
る星を,×印はどちらの星座に属するかわからない星を,それぞれ表す.





                         星座– 2 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                      Contest Day 2 – Constellation





 この入力に対する答えは,星3 が星座A に属する場合と星座B に属する場合の2 通りであり,それぞれ
の場合の星座の図の一例を以下に示す.星3 が星座A に属する場合,星座A の線分の引き方は何通りか考
えられるが,それらすべてをまとめて1 通りと数えることに注意せよ.

       星3 が星座A に属する場合            星3 が星座B に属する場合





                         星座– 3 / 3