Вдоль какой линии
Эпицентры сильных землетрясений не рассыпаны по планете как попало: они вытягиваются вдоль границ литосферных плит. Нужно найти направление, вдоль которого облако эпицентров вытянуто сильнее всего, — первую главную компоненту — и какую долю разброса точек оно объясняет.
Даны n точек плоскости. Для единичного направления u разброс вдоль него — средний квадрат отклонения проекций точек на u от их среднего. Найдите направление u, где разброс наибольший, и выведите угол между u и осью x, отсчитанный против часовой стрелки, в градусах от 0 до 180 (направления u и −u — одно и то же). Вторым числом выведите долю: наибольший разброс, делённый на сумму разбросов вдоль x и вдоль y.
Тесты с третьего по пятый — настоящие эпицентры землетрясений магнитудой от 5 за 2015–2025 годы из каталога USGS в трёх поясах; координаты — километры к востоку и к северу от далёкой точки.
Вход
В первой строке n (1 ≤ n ≤ 10⁵), дальше n строк с целыми координатами x, y (по модулю не больше 10⁶).
Выход
Угол и доля через пробел; угол проверяется с точностью 10⁻⁶ градуса (0 и 180 — одно и то же), доля — с точностью 10⁻⁶. Если разброс одинаков во всех направлениях — облако «круглое», и такого направления нет, — выведите -.
Примеры
Пример 1
6 100 102 104 105 108 107 111 111 115 113 118 117
39.297813375 0.995535677
Пример 2
4 5 0 -5 0 0 5 0 -5
-
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Разброс вдоль направления u = (cos φ, sin φ) — квадратичная функция от cos φ и sin φ. Через какие три числа она выражается?
2Подсказка 2
Это uTSu для матрицы ковариаций S 2 × 2. Где у квадратичной формы на окружности максимум?
3Идея
Пусть a — дисперсия по x, b — по y, c — ковариация. Разброс вдоль φ равен a cos²φ + 2c sin φ cos φ + b sin²φ = (a + b)/2 + ((a − b)/2)·cos 2φ + c·sin 2φ. Это синусоида от 2φ, и её максимум — при 2φ = atan2(2c, a − b). Наибольшее значение — (a + b)/2 плюс амплитуда √(((a − b)/2)² + c²): это большее собственное значение матрицы ковариаций, а a + b — сумма обоих. Если a = b и c = 0, амплитуда нулевая, и все направления равны.
4Разбор
Главное — центрировать: разброс считается относительно центра масс облака. Чтобы проверка «облако круглое» была точной, удобно считать в целых числах величины n²·a = nΣx² − (Σx)², n²·b и n²·c = nΣxy − ΣxΣy: общий множитель n² не меняет ни угла, ни доли. В Python целые числа не переполняются, в Go эти произведения доходят до 10²² и не помещаются в int64 — нужен math/big или 128-битная арифметика. Разность a − b тоже лучше брать точно и только потом переводить в float.
На землетрясениях получаются знакомые по картам линии: пояс вдоль западного края материка вытянут почти с севера на юг (82,5° от направления на восток, 92 % разброса вдоль оси), дуга островов на севере Тихого океана — почти с запада на восток (18,7°, 98 %).
4+Решение
5Сложность
O(n): пять сумм за один проход.
6Типичные ошибки
- Не центрировать. Вторые моменты относительно начала координат вместо центра масс. Для облака вдали от нуля «главная ось» тогда смотрит из начала координат на облако, какой бы формы оно ни было. Ловится уже первым примером.
- atan вместо atan2. atan(2c/(a − b)) не различает, какое из двух перпендикулярных направлений — максимум, а какое — минимум, и падает при a = b.
- Угол вне [0, 180). Направление без знака: −30° и 150° — одна ось, и выводить нужно 150.