E. Хөгжилтэйгээр тойрог зур

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$S$ цэгийн олонлог координатын хавтгай дээр оршино. $S$ олонлог координатын эх болох $O(0, 0)$ цэгийг агуулахгүй, мөн $A$ ба $B$ олонлогийн ялгаатай цэг болгоны хувьд $OAB$ гурвалжин эерэг талбайтай.

Бид ($P_1, P_2), (P_3, P_4), ... , (P_{2k-1}, P_{2k}$) хос цэгүүдийг агуулсан олонлогийг дараах нөхцлийг хангаж байвал сайн олонлог гэе. Үүнд:

  • $k ≥ 2$.
  • Бүх $S$-ын элемент $P_i$-ууд ялгаатай.
  • Ямар ч хоёр хос ($P_{2i-1},P_{2i}$), ($P_{2j-1},P_{2j}$)-ын хувьд $OP_{2i-1}P_{2j-1}, OP_{2i}P_{2j}$ гурвалжингуудыг багтаасан тойргуудад ерөнхий цор ганц цэг байх ба $OP_{2i-1}P_{2j-}, OP_{2i}P_{2j-1}$ гурвалжингуудыг багтаасан тойргуудад ерөнхий цор ганц цэг байна.

Хосуудыг агуулсан сайн олонлогийн тоог $1000000007$ ($10^9 + 7$)-д хуваахад гарах үлдэгдэлийг ол.

Оролт

Эхний мөр $S$ дээрх цэгийн тоо $n$ ($1 ≤ n ≤ 1000$)-г агулна. Дараагийн $n$ ширхэг мөр бүр 4 $a_i$, $b_i$, $c_i$, $d_i$ ($0 ≤ |a_i|, |c_i| ≤ 50$; $1 ≤ b_i, d_i ≤ 50$; ($a_i, c_i) ≠ (0, 0)$) тоог агуулна. Эдгээр тоонуууд нь цэгийг илэрхийлнэ. Ямар ч хоёр цэг давхцахгүй.

Гаралт

Бодлогын хариуг $1000000007$ ($10^9 + 7$)-д хуваахад гарах үлдэгдэлийг хэвлэ.

Орчуулсан: Баттулга

Жишээ тэстүүд

Оролт
10
-46 46 0 36
0 20 -24 48
-50 50 -49 49
-20 50 8 40
-15 30 14 28
4 10 -4 5
6 15 8 10
-20 50 -3 15
4 34 -16 34
16 34 2 17
Гаралт
2
Оролт
10
30 30 -26 26
0 15 -36 36
-28 28 -34 34
10 10 0 4
-8 20 40 50
9 45 12 30
6 15 7 35
36 45 -8 20
-16 34 -4 34
4 34 8 17
Гаралт
4
Оролт
10
0 20 38 38
-30 30 -13 13
-11 11 16 16
30 30 0 37
6 30 -4 10
6 15 12 15
-4 5 -10 25
-16 20 4 10
8 17 -2 17
16 34 2 17
Гаралт
10
Орчуулгыг засах?
Сэтгэгдлүүдийг ачааллаж байна...