Макака и Бананы

시간 제한3초메모리 제한1024 MB

요약
각 삼각형에서 표시된 꼭짓점이 y좌표 최솟값이 되는 회전각 구간을 구한 뒤, 가장 많은 삼각형이 겹치는 각도를 찾는다.
난이도

어려움10점 중 8점

유형
기하, 정렬, 구간, 수학
정답자
아직 제출이 없습니다

문제

Макака Виктор решил испытать удачу и отправился в широко известное в узких кругах <<zino000>>, где он планирует опробовать новейший игровой автомат.

Автомат устроен очень просто: макака дергает за канат, чем приводит во вращение основной барабан (смотрите рисунок), внутри которого находятся nn слоёв, расположенных перпендикулярно оси вращения барабана. В каждом слое находится жёстко закреплённый невырожденный треугольник. Таким образом, все треугольники вращаются вокруг оси барабана с одинаковой угловой скоростью. Внутри каждого треугольника расположен шарик пренебрежимо малого размера, который под действием гравитации скатывается в одну из вершин с минимальной текущей координатой yy.

Ровно одна из вершин каждого треугольника является выигрышной. Если после остановки барабана шарик попадает в выигрышную вершину, то макака получает одну монету. При этом, если в момент остановки барабана у треугольника оказалось несколько вершин с минимальной координатой yy, и одна из них является выигрышной, то Виктору обязательно повезёт и он получит монету.

После нескольких игр Виктор научился останавливать вращение автомата в произвольный момент времени с помощью ловкого пинка. Теперь он хочет знать, какое максимальное количество монет он может выиграть, если правильно выберет момент, когда прекратить вращение конструкции.

입력

В первой строке записано единственное число nn (1≤n≤200,0001 \le n \le 200\\,000) ---количество треугольников в барабане.

В каждой из последующих ii строк содержится шесть целых чисел x_1,ix\_{1, i}, y_1,iy\_{1, i}, x_2,ix\_{2, i}, y_2,iy\_{2, i}, x_3,ix\_{3, i}, y_3,iy\_{3, i} ---координаты точек треугольника в ii-м слое барабана. Координаты даны в плоскости, ортогональной оси вращения барабана, при этом ось вращения проходит через точку (0,0)(0, 0). Выигрышной является первая вершина каждого из треугольников. Все координаты целые и по модулю не превосходят 10910^9. Гарантируется, что все треугольники являются невырожденными (то есть, площадь каждого треугольника строго больше нуля).

출력

В единственной строке выведите максимальное количество монет, которое может получить макака Виктор, если правильно выберет момент времени, когда число выигрышных вершин, обладающих минимальной yy-координатой среди вершин своего треугольника, максимально.

힌트

Во втором примере одним из оптимальных решений будет остановить барабан в самом начале. Тогда выигрышная вершина окажется одной из нижних для треугольников на первом и третьем слое.

예제2

  1. 예제 1

    입력
    3
    0 0 2 0 1 2
    3 1 5 2 5 0
    7 2 6 0 8 0
    
    예상 출력
    3
    
  2. 예제 2

    입력
    4
    0 0 1 0 0 1
    0 0 1 0 0 -1
    0 0 -1 0 0 1
    0 0 -1 0 0 -1
    
    예상 출력
    2