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



可复制的 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