問題一覧 > 通常問題

No.1625 三角形の質問

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 37
作問者 : null / テスター : chineristAC sak
お気に入りにしたユーザー ProblemId : 5369 / 自分の提出
問題文最終更新日: 2022-04-25 23:40:59
Triangle Queries
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 306 (順位表) の他の問題:

Problem Statement

You are given $n$ triangles on the $xy$-plane. The $i$-th triangle has vertices $(a_i, b_i), (c_i, d_i), (e_i, f_i)$.

A total of $q$ queries are given. Each query has one of the following formats.

  • $1\ a\ b\ c\ d\ e\ f$: Add a triangle with vertices $(a, b), (c, d), (e, f)$.
  • $2\ l\ r$: Among the triangles that are entirely contained in $[l, r]$ with respect to the $x$-coordinate (more formally, those satisfying $l \le \min (a, c, e) \land \max (a, c, e) \le r$), find the triangle with the maximum area and print twice its area (an integer). If no triangle satisfies the condition, print -1.
    • Process the queries in order.

    Constraints

  • $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$
  • For every given triangle, its points are not collinear.
  • All input values are integers.

    • Input

    $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$

    Here, $query$ has one of the following formats. 

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

    Output

    For each query of type $2$, print the answer. Print a newline at the end.

    Sample

    Sample 1
    Input
    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
    Output
    1
1
2
9
999999998000000001
-1
22

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