I have been thinking about the problem these days, and found that the solution is much related to the 4, 5 or 6-point groups of the N points. For the former two situations, we could simply calculate that the total number of the figures is 4 * C(n, 4) and 5 * C(n, 5) but what have we do when there are 6-point groups? According to the problem statement, the chords must intersect pairwise, so the solution for 6-point groups will be based on the detail position of the points. For example, we must find out if the chords will parallel with each other. On the other side, I found we have more than one ways to connect 6 points to form the figure. For those 6-point groups with no paralleling chords, we have actually 4 ways to connect them: (1-4, 2-5, 3-6), (1-4, 2-6, 3-5), (2-5, 1-3, 4-6) and (3-6, 1-5, 2-4). Here we numbered the points in CW or CCW order. Could anybody tell me that why the correct answer could be 4 * C(n, 4) + 5 * C(n, 5) + C(n, 6), (especially the last term) If my analysis above is right, this formula will be wrong even in N = 7. Thanks in advance. I think that's indeed the correct answer. For any 4-point group we have 4 combinations, and for any 5-point groups we have 5. So there are 4 * C(7 ,4) + 5 * C(7, 5) = 245. For any 6-point groups, as N = 7, we could know that it is a complete group for all 7 points with only one missing. So the 7 "different" groups are actually the same. Let's count how many interesting triangles in one group. For they are all the same, we take point 1, 2, 3, 4, 5, 6 on the circle, which is in CCW order (7 is missing). We have the following two ways to connect them and make them intersect pairwise: (1-4, 2-5, 3-6): a small triangle is formed inside the circle. and (1-3, 2-5, 4-6): a long triangle is formed, with 2 of its vertices inside the circle. So, there are 2 (or, at least 2) combinations for every 6-point groups in N = 7. So the total number will be 245 + 7 * 2 = 259 (or, at least 259). But all the ACed program will give the answer 252. Why? Where did I have a mistake? Anyone, please, tell me the truth about this problem. Thanks again in advance! 3 of your ways to connect 6 points are wrong: (1-4,2-6,3-5) - segments 2-6 and 3-5 don't intersect (2-5,1-3,4-6) - segments 1-3 and 4-6 don't intersect (3-6,1-5,2-4) - segments 1-5 and 2-4 don't intersect It is true, because any six different points construct a CONVEX 6-gon if they lie on one circle. Well, I suddenly realized that we should regard the CHORD as a SEGMENT, not a LINE. So the ACed programs are right. Thank you very much. Let S4(n),S5(n),S6(n)- number of different 4-poligons,5-poligons and 6-poligons in n poligon. I have AC using formula F(n)=4*S4(n)+5*S5(n)+S6(n). But this formula can not be right because in different 6-poligons 3 hords may intersect in the same point and this triangle will be counted more the once. Your worry is superfluous This condition (put mentally n points on its periphery at equal distances) can guarantee that there will not be different 6-poligons 3 hords may intersect in the same point and this triangle will be counted more the once P.S My English is so poor... My suspictions based on considering ideal 12-poligon in which exist two ideal 6- sub-poligons which different and distinvished by rotation and having common centre in which their hord intersected. Edited by author 01.11.2007 22:26 I doubt anyone can mentally put 2000 points on a circle =) Hah, I on the other hand believe everyone can mentally (and not only) put infinitely many points on a circle. After all - isn't that the definition of a circle? (Infinitely many points with equal distance from one other point - the center?) :D F(n)=4*S4(n)+5*S5(n)+S6(n) Why is it true and how to guess about it? a picture is needed to understand ! please assist Yes, I was thinking about it too and I understand it now. In fact, it's said in statement that interesting triangle is not a triangle but "any three different chords from this set that intersect pairwise" and "at least one of their intersection points lies inside the circle". Therefore, three segments intersecting in one point are interesting triangle( and not a triangle). It's like saying that interesting triangle is a four-sided figure =) Unfortunaly, test cases allows using of one wide - known method :) The answer is of course P(n), and P(n) hasn't more than x^6. 3: 0 4: 4 5: 25 6: 91 7: 252 8: 588 ... 1000: 1409590423741500 Edited by author 29.10.2007 02:57 can anyone send algorithm of this problem on my mail? gio-saghinadze@mail.ru thanks Edited by author 30.10.2007 17:42 Edited by author 30.10.2007 18:07 I'm sorry, but could you give answer fo 2000? I have WA10 with correct answer for 1000 and I have no idea what can be wrong. For 2000: 89553445611633000 It's enough the pascal's extended type to solve this problem. But the C++'s double type has only 15 digits :'( Edited by author 16.11.2007 01:58 Use long double! I think it's enough int64 I agree with topic), but i think it depends on compiler VS help says that long double equals to double and have 15 digits, but actually can store up to 18 strange.. Int64 is enougth Pascal - это наше всё... If you can't normaly solve the problem, just agree with it. C++ - the best! Pascal - already died. gcc has 10 bytes for long double while VC long double is 8 bytes long. Anyway, __int64 can hold up to 18 digits. And keep it unsigned :) Am i right that it's not important that some three hords intersect at the same point, and this figure is according to condition of promlem? For example, three diagonals of ideal 6-polygon which intersects at its center make an interesting triangle, aren't they? Thank's. VS6.0 has very stupid compiler :) Edited by author 18.11.2007 21:28 when you submit your code you can use option "reply to this email" maybe you use Visual Studio 6.0 and it's stupid compiler for (int i=0;i<k;i++) // there you define i { tmp*=n; n--; } // end of area where i is visible for (i=1;i<=k;i++) ^^^^^^^^^^ i is undefined there { d*=i; } in c++ standart you can do such cicles for (int i = 0; i < 4; i++) ..... for (int i = 0; i < 4; i++) ..... but stupid VS 6.0 compiler think that it is wrong anyway you can do as this: int i; for (i = 0; i < 4; i++) ... for (i = 0; i < 4; i++) ... Edited by author 18.11.2007 13:27 what answare on input = 6 Yep, and for 7 8 9 10 give some answers too plz:) Btw, why when n = 5 ans answer is 25. Somehow I managed to find 28 trianles. |
|