시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 62 | 31 | 31 | 58.491% |
Joana Vasconcelos is a Portuguese artist who uses everyday objects in her creations, like electric irons or plastic cutlery. She is an inspiration to Ana, who wants to make ceiling hanging sculptures with straight knitting needles and balls of wool. For safety reasons, there will be a ball at each end of each needle. Knitting needles vary in colour, length and thickness (to allow intersections of needles).
Sculptures are to be exhibited in room corners, which provide a 3D Cartesian coordinate system, with many lamps on the ceiling. Sculpture design are made with the coordinates of the centres of the balls of wool in which knitting needles are stuck. That is, each needle N is represented by a set of two different triples: N={(x,y,z), (x',y',z')}.
Ana dislikes closed chains. A true closed chain is a sequence of k distinct needles, N1, N2, ..., Nk (for some k ≥ 3), such that:
But her dislike of closed chains is so extreme that the shadow of the sculpture on the floor has to be free of "floor closed chains". Given any needle N={(x,y,z), (x',y',z')}, let N↓ = {(x,y), (x',y')} denote the shadow of needle N on the floor. For Ana (who is an artist), a floor closed chain is also a sequence of k distinct needles, N1, N2, ..., Nk (for some k ≥ 3), such that:
Consider the sculpture depicted in the figure, which has the following four knittinf needles:
A = {(12,12,8), (10,5,11)}, B = {(12,12,8), (4,14,21)}, C = {(12,12,8), (12,20,8)}, D = {(4,14,21), (10,5,21)}.
This structure is not free of closed chains because, although there is no closed chain, the sequence of needles A,B,D is a floor closed chain.
Write a program that, given the knitting needles of a sculpture, determines whether there is a true or a floor closed chain in the sculpture.
The first line of the input has one integer, K, which is the number of knittinf needles in the sculpture. Each of the following K lines contains six integers, x1, y1, z1, x2, y2, and z2, which indicate that {(x1,y1,z1), (x2,y2,z2)} is the set of triples of a needle. Any two distinct needles are represented by different sets of triples.
The output has two lines, each one with a string. The string in the first line is: True closed chains, if there is some true closed chain in the sculpture; No true closed chains, otherwise. The string in the second line is: Floor closed chains, if there is some floor closed chain in the sculpture; No floor closed chains, otherwise.
4 12 12 8 10 5 11 12 12 8 4 14 21 12 12 8 12 20 8 4 14 21 10 5 21
No true closed chains Floor closed chains
4 1 1 1 2 2 2 2 2 2 1 5 5 9 4 4 9 4 2 9 4 4 9 9 4
No true closed chains No floor closed chains
3 50 50 50 100 100 100 100 100 100 50 50 90 50 50 90 50 50 50
True closed chains No floor closed chains
3 1 1 5 1 3 7 1 3 7 4 4 5 4 4 5 1 1 5
True closed chains Floor closed chains
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2016 K번