양친매성 탄소 분자 (ACM)

상하이 하이퍼컴퓨터스(Shanghai Hypercomputers)는 세계 최대의 컴퓨터 칩 제조사로, 양친매성 탄소 분자(Amphiphilic Carbon Molecules, ACM) 라는 새로운 종류의 나노 입자를 발명했다. ACM은 반도체여서 전자의 도체가 될 수도, 부도체가 될 수도 있는데, 이는 컴퓨터 칩 산업에서 매우 중요한 성질이다. 또한 ACM은 양친매성이라 분자의 일부는 친수성이고 나머지는 소수성이다. 친수성 ACM은 물과 같은 극성 용매에는 녹지만 아세톤과 같은 비극성 용매에는 녹지 않는다. 소수성 ACM은 반대로 아세톤에는 녹지만 물에는 녹지 않는다. 물이든 아세톤이든 어느 용매에라도 녹은 ACM은 칩 제조 공정에 사용할 수 있다.

재료 공학자인 당신의 임무는 작업대 위에 흩어진 ACM 입자를 가능한 한 많이 녹이는 것이다. 두 용액이 섞이지 않도록, 곧고 충분히 긴 절연 탄소 칸막이 카드(Insulating Carbon Partition Card, ICPC) 하나를 작업대 위에 세워 입자들을 두 쪽으로 완전히 나눈다. 그런 다음 한쪽에는 물을, 다른 쪽에는 아세톤을 붓는다.

그림 1

입자는 다음 경우에 녹는다.

• 친수성 입자가 물 쪽에 있을 때,
• 소수성 입자가 아세톤 쪽에 있을 때,
• 또는 입자가 칸막이 카드 위(경계선) 에 정확히 놓여 있을 때 — 카드 바로 아래의 입자는 경계에 있으므로 종류에 관계없이 녹는다.

반대로 아세톤 쪽에 있는 친수성 입자나 물 쪽에 있는 소수성 입자는 녹지 않는다.

작업대 위쪽의 디지털 카메라가 모든 입자의 정확한 위치와 종류를 2차원 사진의 점으로 알려 주며, 칸막이 카드는 사진에서 하나의 직선으로 나타난다. 녹는 입자의 수가 최대가 되도록 이 직선(카드)을 놓을 위치를 정하라.

그림 2

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 ACM 입자의 개수를 나타내는 정수 $N$이 적힌 줄로 시작한다. 이어지는 $N$개의 줄에는 각각 세 정수 $x$, $y$, $r$가 주어진다. $(x, y)$는 2차원 사진에서 입자의 위치이고, $r$는 입자의 종류로 $0$이면 친수성, $1$이면 소수성을 뜻한다. $x$와 $y$의 절댓값은 $10000$ 이하이고, $N$은 $1000$ 이하이다. 테스트 케이스는 최대 $10$개이다. $N = 0$인 줄은 입력의 끝을 나타내며 처리하지 않는다.

위의 그림 2는 아래 세 번째 예제에 대한 입자들의 위치와 최적의 칸막이 카드 위치를 보여 준다.

각 테스트 케이스마다, 녹일 수 있는 ACM 입자의 최대 개수를 정수 하나로 한 줄에 출력한다.