Олимпиадный тренинг

Задача 38131. Permutation

Задача

Besi has N (3≤N≤40) favorite points on a 2D lattice, no three of which are collinear. For each 1≤i≤N, the i-th point is given by two integer coordinates x_i and y_i (0≤x_i,y< sub>i≤10⁴).
Besi draws some lines between the points like this:

It selects some permutation p₁,p₂,…,p_N from N points
It draws segments between p₁ and p₂, p₂ and p₃, p_{3< /sub> and p₁.

Then for each integer i from 4 to N in order, it draws line segments from p_i to p_j for all j<i so that this line segment does not intersect any of the previously line segments drawn (outside endpoints)

Besi noticed that for each i, she drew exactly three new segments. Calculate the number of permutations Besi could have chosen in step 1 that satisfy this property modulo 10⁹+7.

Input:

The first line contains N.

Each of the following N lines contains two space-separated integers x_i and y_i.

Output:

Number of permutations modulo 10⁹+7.

Examples

#
Input
Output
Explanation

1
4

0 0

04

1 1

1 2
0
No swapping will work.

2
4

0 0

04

40

1 1
24
All permutations work.

3
5

0 0

04

40

1 1

1 2
96
One of the permutations that satisfies the property - (0,0),(0,4),(4,0),(1,2),(1,1).

For this permutation

First, it draws lines between each pair of (0,0),(0,4), and (4,0).
It then draws lines from (0.0), (0.4), and (4.0) to (1.2).
Finally, it draws lines from (1,2), (4,0), and (0,0) to (1,1).

Pattern:

A permutation does not satisfy a property if its first four points are (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), and (0,4)(0,4) in some order.}

#	Input	Output	Explanation
1	4 0 0 04 1 1 1 2	0	No swapping will work.
2	4 0 0 04 40 1 1	24	All permutations work.
3	5 0 0 04 40 1 1 1 2	96	One of the permutations that satisfies the property - (0,0),(0,4),(4,0),(1,2),(1,1). For this permutation First, it draws lines between each pair of (0,0),(0,4), and (4,0). It then draws lines from (0.0), (0.4), and (4.0) to (1.2). Finally, it draws lines from (1,2), (4,0), and (0,0) to (1,1). Pattern: A permutation does not satisfy a property if its first four points are (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), and (0,4)(0,4) in some order.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Ваш ответ

Прикрепите файл с исходным кодом программы:

или выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет

Study

Profile

Задача 38131. Permutation

Задача

Examples

Комментарий учителя

Ваш ответ

Загруженные файлы