{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eНедавно исследователи обнаружили древний манускрипт, который описывает некоторое созвездие. Из него следует, что созвездие состоит из \u003cstrong\u003eM\u003c/strong\u003e звёзд, а также известны расстояния между каждой парой звёзд созвездия, если рассматривать небо как плоскость, а звёзды --- как точки на этой плоскости.\u003c/p\u003e\n\n\u003cp\u003eНа сегодняшнем небе в том полушарии, где предположительно находится описанное созвездие, видно \u003cstrong\u003eN\u003c/strong\u003e звёзд. Обычно созвездием считают объединение самых ярких звёзд какого-либо фрагмента неба, но за прошедшие тысячелетия яркости звёзд могли измениться, поэтому опираться на этот показатель уже невозможно. Следовательно, определять, какие звёзды сегодняшнего неба могут образовывать описанное в манускрипте созвездие, приходится лишь на основе данных расстояний.\u003c/p\u003e\n\n\u003cp\u003eБудем называть \u003cem\u003eвозможным местоположением созвездия\u003c/em\u003e список звёзд (\u003cstrong\u003eI_1\u003c/strong\u003e, \u003cstrong\u003eI_2\u003c/strong\u003e, ..., \u003cstrong\u003eI_M\u003c/strong\u003e) такой, что для каждого \u003cstrong\u003ei\u003c/strong\u003e и \u003cstrong\u003ej\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ei\u003c/strong\u003e, \u003cstrong\u003ej\u003c/strong\u003e ≤ \u003cstrong\u003eM\u003c/strong\u003e) расстояние между звёздами \u003cstrong\u003eI_i\u003c/strong\u003e и \u003cstrong\u003eI_j\u003c/strong\u003e равно расстоянию между \u003cstrong\u003ei\u003c/strong\u003e-ой и \u003cstrong\u003ej\u003c/strong\u003e-ой звёздами манускрипта. Два возможных местоположения различны, если хотя бы на одной из позиций в них записаны разные звёзды.\u003c/p\u003e\n\n\u003cp\u003eВам задано множество звёзд на сегодняшнем небе. Также дана матрица размерности \u003cstrong\u003eM\u003c/strong\u003ex\u003cstrong\u003eM\u003c/strong\u003e, где элемент (\u003cstrong\u003ei\u003c/strong\u003e, \u003cstrong\u003ej\u003c/strong\u003e) обозначает квадрат расстояния между звёздами \u003cstrong\u003ei\u003c/strong\u003e и \u003cstrong\u003ej\u003c/strong\u003e созвездия. Подсчитайте количество возможных местоположений этого созвездия.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eПервая строка входного файла содержит число \u003cstrong\u003eM\u003c/strong\u003e. Следующие \u003cstrong\u003eM\u003c/strong\u003e строк содержат по \u003cstrong\u003eM\u003c/strong\u003e целых чисел каждая --- матрицу расстояний. Далее записано число \u003cstrong\u003eN\u003c/strong\u003e, а затем следует \u003cstrong\u003eN\u003c/strong\u003e строк, каждая из которых содержит пару целых чисел \u003cstrong\u003eX_i\u003c/strong\u003e, \u003cstrong\u003eY_i\u003c/strong\u003e --- координаты \u003cstrong\u003ei\u003c/strong\u003e-ой звезды на сегодняшнем небе.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e2\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e ≤ \u003cstrong\u003e30000\u003c/strong\u003e, \u003cstrong\u003e2\u003c/strong\u003e ≤ \u003cstrong\u003eM\u003c/strong\u003e ≤ \u003cstrong\u003emin(N, 20)\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eКоординаты каждой звезды --- целые числа, не превосходящие \u003cstrong\u003e10000\u003c/strong\u003e по абсолютному значению. Никакие две звезды не находятся в одной точке.\u003c/p\u003e\n\n\u003cp\u003eЗаданная матрица расстояний симметрична, её главная диагональ содержит только нули, а все остальные числа положительные и не превосходят \u003cstrong\u003e10^18\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВыведите количество возможных местоположений созвездия из манускрипта.\u003c/p\u003e\n\n"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n0 1 2\n1 0 1\n2 1 0\n4\n0 0\n1 0\n0 1\n1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}