eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Герцогиня

Герцогиня

Лакей-Лящ вийняв з-під пахви величезний лист (величиною з нього самого, не менше) і передав його Жабенятку. -- \textit{Герцогині}, -- промовив він з надзвичайно важністю. -- \textit{Від Королеви. Запрошення на крокет.} Жабенятко взяло листа і так само важно повторив його слова, лише трішки змінивши їх порядок: \textit{-- Від Королеви. Герцогині. Запрошення на крокет.} Пригоди Аліси в країні чудес (переклад Н.М. Демурової) \includegraphics{https://static.e-olymp.com/content/23/2398414a64e31b872a6e52f72fb8819fcfcab219.jpg} Отже, Герцогиня готується до королевського крокету і ш'є собі корсет (корсет для крокета). На корсеті предбачені отвори для шнурівки, всього \textbf{N}+\textbf{M} отворів. Розміщені вони в \textbf{2} ряди: в одному ряду \textbf{N} отворів, а у другому -- \textbf{M}. Шнурівка дуже складна -- спеціальні стяжки з'єднують отвори з першого ряду з отворами з другого ряду, утворюючи при цьому величезну кількість перетинів між рядами. Герцогиня у відчаї -- їй обов'язково потібно знати це число! Адже вона не бажає образити Королеву своїм невіглаством. Звичайно, Герцогиню симпатичним героєм назвати важко -- достатньо поглянути на портрет <<Потворної Герцогині>> художника \textbf{XVI} століття Квінтена Массейна. Скоріше всього ця Маргарита Маульташ, герцогиня Карінтії і Тиролю (\textbf{XIV} ст.) і стала прообразом для перших рисунків Герцогині в "Алісі в країні чудес". Проте допомогти Герцогині потрібно. Будемо вважати, що \textbf{N} точок у першому ряду мають координати (\textbf{0},\textbf{1}), (\textbf{0},\textbf{2}), ..., (\textbf{0},\textbf{N}), а \textbf{M} точок у другому ряду мають координати (\textbf{1},\textbf{1}), (\textbf{1},\textbf{2}), ..., (\textbf{1},\textbf{M}). Деякі точки з різними абсцисами з'єднані відрізками, потрібно визначити, скільки існує різлних пар відрізків, які між собою перетинаються. \InputFile У першому рядку записані числа \textbf{N}, \textbf{M}, \textbf{K}, де \textbf{K} -- це кількість відрізків між точками (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{300}, \textbf{1} ≤ \textbf{K} ≤ \textbf{N*M}). У наступних \textbf{K} рядках записано по два числа \textbf{X} і \textbf{Y}, які означають, що з'єднано відрізки з координатами (\textbf{0},\textbf{X}) и (\textbf{1},\textbf{Y}). Всі відрізки у вхідному файлі різіні. \OutputFile Виведіть кількість пар відрізків, які перетинаються. Якщо відрізки дотикаються кінцями, то це не враховується за перетин.
Ліміт часу 0.25 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
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

...
Вихідні дані #1
2011522500
Автор Соболєв Євген, Соболєв Дмитро
Джерело VI Open Cup Kharkov 14.03.2010