#PQJ1554x1406. QOJ 1554_1406

    ID: 2662 传统题 9000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训组合数学计算几何

QOJ 1554_1406

Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Constellation 2 2 人の星座(Constellation 2) JOI ちゃんとIOI ちゃんは親友同士である.ある日,JOI ちゃんとIOI ちゃんは山の上にある展望台で天 体観測をすることにした. 展望台では,N 個の星を観測することができる.それぞれの星には1 からN まで番号が付いていて,そ れぞれの星は,赤色,青色,黄色のいずれかの色をしている. この展望台で観測された星は座標平面上の点で表される.この座標平面において,星i (1 ≦i ≦N) に対 応する点はPi(Xi, Yi) である.座標平面上の点P1, . . . , PN は,どの2 点も異なる.また,点P1, . . . , PN は, どの3 点も同一直線上にない. JOI ちゃんとIOI ちゃんは,JOIOI 座という星座を作ることにした.まず2 人は,赤色,青色,黄色の 3 つの星を結んだ三角形を使うことを考えた.このような三角形のことを良い三角形と呼ぶ. 2 人は,以下の条件を満たす2 つの良い三角形の組(順序を問わない)をJOIOI 座の候補とすることに した. • 2 つの良い三角形(三角形の周および内部)には共有点がない.すなわち,2 つの良い三角形同士が 重なったり,一方が他方に含まれることはない. 条件を満たす例 条件を満たさない例 JOI ちゃんとIOI ちゃんは,JOIOI 座の候補として考えられるものがいくつあるか数えることにした.た だし,JOIOI 座の候補を構成する6 個の星が一致していても,良い三角形の結び方が異なる場合は,それ らを別の候補として数えるものとする. 課題 展望台で観測された星の情報が与えられたとき,JOIOI 座の候補の総数を出力するプログラムを作成せよ. 2 人の星座– 1 / 5 Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Constellation 2 入力 標準入力から以下のデータを読み込め. • 1 行目には整数N が書かれている.これは展望台で観測された星の個数がN であることを表す. • 続くN 行のうちのi 行目(1 ≦i ≦N) には,3 つの整数Xi, Yi,Ci が空白を区切りとして書かれている. これは,星i の座標がPi(Xi, Yi) であることを表し,Ci は星i の色を表している.星i の色は,Ci が 0 なら赤色であり,1 なら青色であり,2 なら黄色である. 出力 標準出力に,JOIOI 座の候補の総数を表す整数を1 行で出力せよ. 制限 すべての入力データは以下の条件を満たす. • 6 ≦N ≦3 000. • −100 000 ≦Xi ≦100 000. • −100 000 ≦Yi ≦100 000. • 0 ≦Ci ≦2. • どの色の星も1 個以上存在する. • Pi , Pj (1 ≦i < j ≦N) • Pi, P j, Pk は同一直線上にない(1 ≦i < j < k ≦N). 2 人の星座– 2 / 5 Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Constellation 2 小課題 小課題1 [15 点] • N ≦30 を満たす. 小課題2 [40 点] • N ≦300 を満たす. 小課題3 [45 点] 追加の制限はない. 入出力例 入力例1 出力例1 7 4 0 0 0 2 0 1 1 2 2 -2 1 0 -2 -3 0 0 -2 1 2 -2 2 この入力例では,星の配置は下図のようになる.この図において,赤色の星は丸,青色の星は菱型,黄 色の星は三角形で表す. 2 人の星座– 3 / 5 Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Constellation 2 この入力例では,JOIOI 座の候補は以下に示す4 つである. 条件を満たす4 つの例 2 人の星座– 4 / 5 Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Constellation 2 入力例2 出力例2 8 12 16 0 0 17 0 0 0 7 2 0 -7 2 -1 -1 1 -1 1 2 -6 4 1 -6 -4 1 入力例3 出力例3 21 7748 1 20 0 4 20 0 0 22 0 5 22 0 6 25 0 8 25 0 4 26 0 11 11 1 7 12 1 14 13 1 8 15 1 15 16 1 11 17 1 18 0 2 13 2 2 16 2 2 19 4 2 18 6 2 21 8 2 24 8 2 19 10 2 2 人の星座– 5 / 5