33441번 - Collinear Arrangements 다국어

문제

Given a convex polygon of $n$ points $P_1, P_2, \ldots, P_n$ on a two-dimensional plane, answer $q$ queries, where each query has one of the following types:

1. Given one point $(x, y),ドル find the number of pairs $(P_i, P_j)$ such that 1ドル \le i < j \le n$ and the three points $(x, y),ドル $P_i,ドル and $P_j$ are collinear.
2. Given two points $(x_1, y_1)$ and $(x_2, y_2),ドル find the number of points $P_i$ such that 1ドル \le i \le n$ and the three points $(x_1, y_1),ドル $(x_2, y_2),ドル and $P_i$ are collinear.

입력

The first line contains two integers $n$ and $q$ (3ドル \le n \le 10^5,ドル 1ドル \le q \le 10^5$) denoting the number of vertices in the given polygon and the number of queries, respectively.

Each of the following $n$ lines contains two integers, $x$ and $y,ドル denoting a vertex of the polygon.

Each of the following $q$ lines contains one query, which is in one of the following formats:

1. "1 $x$ $y$", asking to calculate the number of pairs $(P_i, P_j)$ such that 1ドル \le i < j \le n$ and the three points $(x, y),ドル $P_i,ドル and $P_j$ are collinear.
2. "2 $x_1$ $y_1$ $x_2$ $y_2$", asking to calculate the number of points $P_i$ such that 1ドル \le i \le n$ and the three points $(x_1, y_1),ドル $(x_2, y_2),ドル and $P_i$ are collinear.

It is guaranteed that:

• $|x|, |y| \le 10^9$ for all points and queries;
• the polygon vertices are given in counter-clockwise order;
• the polygon is convex (in particular, no three vertices are collinear);
• for each query, the given points and the polygon vertices do not coincide;
• the number of queries in the first format does not exceed 100ドル$.

출력

For each query, output a line containing a single integer: the answer to the query.

제한

노트

• For the first query, the only pair is $(P_2, P_5)$ since $(1, 1),ドル $P_2 = (2, 0)$ and $P_5 = (0, 2)$ are collinear.
• For the second query, the only point is $P_1$ since $(1, 1),ドル $(2, 2),ドル and $P_1 = (0, 0)$ are collinear.
• For the third query, the two pairs are $(P_2, P_3)$ and $(P_4, P_5)$.