問題一覧 > 通常問題

No.1625 三角形の質問

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : nullnull / テスター : chineristACchineristAC saksak
0 ProblemId : 5369 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:40:59

問題文

$n$ 個の $xy$ 平面上の三角形が与えられます。$i$ 番目の三角形は $(a_i, b_i), (c_i, d_i), (e_i, f_i)$ を頂点とします。

クエリが合計 $q$ 個与えられます。形式は以下のどちらかです。

  • $1\ a\ b\ c\ d\ e\ f$: $(a, b), (c, d), (e, f)$ を頂点とする三角形を追加する。
  • $2\ l\ r$: $x$ 座標について、$[l, r]$ にすべてが含まれているような三角形 (より形式的には、$l \le \min (a, c, e) \land \max (a, c, e) \le r$ を満たす) のうち 面積が最大 である三角形の 面積の二倍 (整数) を出力する。条件を満たす三角形が存在しない場合は -1 を出力する。
    • 順にクエリを処理してください。

    制約

  • $1 \le n, q \le 10^5$
  • $1 \le a, b, c, d, e, f \le 10^9$
  • $1 \le l \le r \le 10^9$
  • 三角形が与えられる場合、点は同一直線上に存在しない
  • 入力は全て整数

    • 入力

    $n\ q$
$a_1\ b_1\ c_1\ d_1\ e_1\ f_1$
$a_2\ b_2\ c_2\ d_2\ e_2\ f_2$
$\vdots$
$a_n\ b_n\ c_n\ d_n\ e_n\ f_n$
$query_1$
$query_2$
$\vdots$
$query_q$

    ここで、$query$ は以下の形式のどちらかである。 

    $1\ a\ b\ c\ d\ e\ f$
    $2\ l\ r$

    出力

    各クエリ $2$ に対して答えを出力してください。最後に改行してください。

    サンプル

    サンプル1
    入力
    5 8
1 1 1 2 2 1
2 1 2 2 3 1
1 1 1 2 3 1
1 1 10 1 1 2
1 1 1000000000 1 1 1000000000
2 1 2
2 2 3
2 1 3
2 1 10
2 1 1000000000
2 12 34
1 12 1 12 2 34 34
2 12 34
    出力
    1
1
2
9
999999998000000001
-1
22

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。