Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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