상근이와 상근이의 형은 피자를 좋아한다. 오늘 상근이의 형이 여러가지 토핑이 얹힌 피자를 주문했다. 그중에는 상근이가 싫어하는 토핑도 있고, 좋아하는 토핑도 있다. 그리고 좋아하는 토핑 중에서도, 싫어하는 토핑 중에서도 양에 따라 선호도가 다르다.
상근이의 형이 상근이에게 원하는 만큼의 조각을 가져가도 된다고 했다. 즉, 상근이는 피자 중심에서 둘레까지 두 번 잘라서 생기는 두 조각 중 하나를 선택 할 수 있다. 만약, 자르는 선이 토핑을 지나간다면, 그 토핑의 중심이 포함된 토핑 전체를 가져가게 된다.(토핑의 중심을 정확하게 자를 수는 없다.) 따라서 각 토핑은 항상 한쪽 조각에만 완전히 포함된다. 상근이는 자신에게 최대한 유리하게 토핑은 선택하고 싶다.
입력
여러 개의 테스트 케이스가 주어진다.
첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 토핑의 개수 N이 주어진다.
그 다음 N개의 줄에는 세 개의 정수 P,x,y가 주어진다.
P,x,y는 각각 토핑의 선호도, 토핑 중심의 x좌표, 토핑 중심의 y좌표이다.
출력
각 테스트 케이스마다, 상근이가 선택 할 수 있는 조각 중에서 토핑의 선호도의 합이 최대가 되는 값을 한 줄에 출력한다.
제한
1 ≤ T ≤ 25
1 ≤ N ≤ 10⁵
-10⁵ ≤ 선호도 ≤ 10⁵
토핑의 중심 좌표 (x, y)는 피자 내부에 있으며, 피자는 중심이 (0, 0)이고 반지름이 10⁹인 원이다.
lsdas 1년 전 2
제목 : 피자 먹고 기분 피자
상근이와 상근이의 형은 피자를 좋아한다. 오늘 상근이의 형이 여러가지 토핑이 얹힌 피자를 주문했다. 그중에는 상근이가 싫어하는 토핑도 있고, 좋아하는 토핑도 있다. 그리고 좋아하는 토핑 중에서도, 싫어하는 토핑 중에서도 양에 따라 선호도가 다르다.
상근이의 형이 상근이에게 원하는 만큼의 조각을 가져가도 된다고 했다. 즉, 상근이는 피자 중심에서 둘레까지 두 번 잘라서 생기는 두 조각 중 하나를 선택 할 수 있다. 만약, 자르는 선이 토핑을 지나간다면, 그 토핑의 중심이 포함된 토핑 전체를 가져가게 된다.(토핑의 중심을 정확하게 자를 수는 없다.) 따라서 각 토핑은 항상 한쪽 조각에만 완전히 포함된다. 상근이는 자신에게 최대한 유리하게 토핑은 선택하고 싶다.
입력
여러 개의 테스트 케이스가 주어진다.
첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 토핑의 개수 N이 주어진다.
그 다음 N개의 줄에는 세 개의 정수 P,x,y가 주어진다.
P,x,y는 각각 토핑의 선호도, 토핑 중심의 x좌표, 토핑 중심의 y좌표이다.
출력
각 테스트 케이스마다, 상근이가 선택 할 수 있는 조각 중에서 토핑의 선호도의 합이 최대가 되는 값을 한 줄에 출력한다.
제한
1 ≤ T ≤ 25
1 ≤ N ≤ 10⁵
-10⁵ ≤ 선호도 ≤ 10⁵
토핑의 중심 좌표 (x, y)는 피자 내부에 있으며, 피자는 중심이 (0, 0)이고 반지름이 10⁹인 원이다.
(x, y)는 원점이 아니다. ⇔ x≠0,y≠0
여러 토핑이 같은 좌표에 있을 수 있다.
한 세트의 테스트 케이스 입력 크기는 4MB를 넘지 않는다.