Duchess (RU)
Duchess (RU)
Лакей-Лещ вынул из-под мышки огромное письмо (величиной с него самого, не меньше) и передал его Лягушонку.
– Герцогине, – произнес он с необычайной важностью. – От Королевы. Приглашение на крокет.
Лягушонок принял письмо и так же важно повторил его слова, лишь слегка изменив их порядок:
– От Королевы. Герцогине. Приглашение на крокет.
Приключения Алисы в стране чудес (перевод Н.М. Демуровой)
Итак, Герцогиня готовится к королевскому крокету и шьет себе корсет (корсет для крокета). На корсете предусмотрены дырочки для шнуровки, всего N+M дырочек. Расположены они в 2 ряда: в одном ряду N дырочек, а во втором – M.
Шнуровка очень сложная – специальные стяжки соединяют дырочки из первого ряда с дырочками из второго ряда, образуя при этом огромное количество пересечений между рядами. Герцогиня в отчаянии – ей обязательно надо знать это число! Ведь она не желает оскорбить Королеву своим невежеством.
Конечно, Герцогиню симпатичным героем назвать трудно – достаточно взглянуть на портрет «Безобразной Герцогини» художника XVI века Квинтена Массейна. Скорее всего эта Маргарита Маульташ, герцогиня Каринтии и Тироля (XIV в.) и стала прообразом для первых рисунков Герцогини в "Алисе в стране чудес". Однако помочь Герцогине нужно.
Будем считать, что N точек в первом ряду имеют координаты (0,1), (0,2), ..., (0,N), а M точек во втором ряду имеют координаты (1,1), (1,2), ..., (1,M). Некоторые точки с разными абсциссами соединены отрезками, требуется определить, сколько существует различных пар отрезков, которые между собой пересекаются.
Input data
В первой строке записаны числа N, M, K, где K – это количество отрезков между точками (1 ≤ N, M ≤ 300, 1 ≤ K ≤ N*M). В последующих K строках записано по два числа X и Y, которые означают, что соединены отрезки с координатами (0,X) и (1,Y). Все отрезки во входном файле различны.
Output data
Выведите количество пар отрезков, которые пересекаются. Если отрезки касаются концами, то это не учитывается за пересечение.
Examples
300 300 90000 143 34 178 272 213 82 27 178 106 217 138 190 262 143 259 94 221 275 63 220 286 45 73 118 243 145 113 201 93 50 276 297 268 235 113 189 130 257 287 124 189 165 166 232 79 180 220 274 283 229 165 18 94 147 69 12 251 175 297 195 188 12 183 172 294 106 138 251 155 290 35 298 40 197 244 173 45 10 84 158 110 133 237 168 275 286 131 229 30 63 283 254 189 105 170 245 283 76 262 19 157 241 133 18 112 294 237 56 26 275 24 125 59 81 112 252 203 149 157 70 252 280 285 64 292 226 272 203 136 55 294 147 67 174 264 219 245 65 261 261 100 273 88 221 21 248 24 45 215 29 68 154 74 26 167 255 4 122 99 300 187 32 140 280 176 159 138 154 264 252 76 15 253 54 194 159 26 286 3 113 106 222 109 17 140 230 41 299 244 299 31 158 8 74 105 257 236 270 85 92 281 23 295 85 84 125 137 219 236 229 177 15 35 129 248 212 179 252 266 7 41 214 24 266 205 31 293 107 61 284 161 121 93 278 276 80 3 246 184 49 53 190 176 103 220 55 177 211 207 282 252 136 135 80 206 181 22 130 6 54 123 285 144 146 84 46 228 252 ...
2011522500