아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Pyramid Construction

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

요약
삼각형 조각 n개의 세 변 길이가 주어질 때, 네 개를 골라 부피가 양수인 사면체를 만들 수 있는지 판별하고 그 조각 번호를 출력한다.
난이도

보통10점 중 6점

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

문제

As you might know, the Egyptian pyramids are one of the most famous wonders of the world. They were built by aliens in ancient times. The alien Ar'glh flies past Earth to work and back every day and he often makes a stop to admire these magnificent structures and find inspiration.

You see, Ar'glh is an architect and is designing his own pyramid. Fortunately, with the new technology, he doesn't need huge blocks of stone or the countless Egyptian workers' labor. But that still doesn't mean that his task is easy.

Over the past centuries, Ar'glh has assembled nn carbon triangular facets, the ii-th of them has sides of length a_ia\_i, b_ib\_i, and c_ic\_i, respectively. He wants to choose four facets and assemble a pyramid in the shape of a non-degenerate tetrahedron with them. Of course, the facets must fit together perfectly without any deformations or gaps and must not protrude beyond the tetrahedron. The volume of the tetrahedron must be strictly positive.

Help the alien architect determine which four facets he can choose from his set to assemble a pyramid in the shape of a tetrahedron.

입력

The first line containts an integer nn --- the number of triangular facets available to Ar'glh (4≤n≤15004 \leq n \leq 1500).

The ii-th of the following nn lines contains three integers a_ia\_i, b_ib\_i, and c_ic\_i --- the lengths of the sides of the ii-th facet (1≤a_i,b_i,c_i≤10,0001 \leq a\_i, b\_i, c\_i \leq 10\\,000, it is guaranteed that each facet is a valid triangle, i.e. a_i+b_i>c_ia\_i + b\_i > c\_i, a_i+c_i>b_ia\_i + c\_i > b\_i, b_i+c_i>a_ib\_i + c\_i > a\_i).

출력

If Ar'glh can choose four facets from which a tetrahedron can be assembled, the first line must contain the word "Yes". In this case the second line must contain four different integers from 11 to nn --- the numbers of facets that can be used to build. If there are several possible answers, print any of them.

Otherwise, print the word "No".

예제3

  1. 예제 1

    입력
    7
    3 3 3
    3 4 5
    4 5 6
    3 4 3
    3 3 5
    6 5 7
    3 5 5
    
    예상 출력
    Yes
    2 4 5 7
    
  2. 예제 2

    입력
    5
    2 3 4
    3 4 5
    4 5 6
    5 6 7
    6 7 8
    
    예상 출력
    No
    
  3. 예제 3

    입력
    4
    2 3 4
    3 4 2
    3 2 4
    4 2 3
    
    예상 출력
    No