| ENG RUS | Timus Online Judge |
Обсуждение задачи 1469. Не курить!Ade [FDU] Is the segment close or open? [1] // Задача 1469. Не курить! 21 дек 2014 22:52 What the output of? 2 0 0 1 1 1 1 2 2 Nabi Re: Is the segment close or open? // Задача 1469. Не курить! 28 мар 2024 08:06 yes Nabi WA in 11 test help please [1] // Задача 1469. Не курить! 28 мар 2024 02:39 i used redblack tree on python and using a quick input using stdin i passed test 8 time limit and met evening at 11 Nabi Re: WA in 11 test help please // Задача 1469. Не курить! 28 мар 2024 08:03 ok, it was a perpendicular but what about 15 test Teacher30 (Burunduk1) How to cheat and get AC. // Задача 1469. Не курить! 5 апр 2013 17:19 Let project all segments to some line (x,y --> z=ax+by) and try all pairs of segments, which have an intersection of projections. To do it just sort events "open segment", "close segment" and brute force pairs. You will get TL. Yet. Now let try 4 lines: (a,b) = (1,0) (0,1) (1,1) (1,-1). At first, let estimate number of pairs to process for each line in O(nlogn) time. Now that we may choose line, which produces minimal mumber of pairs. AC in 0.937 seconds. id = 4870936. ibra (TNU) Clarification [2] // Задача 1469. Не курить! 20 сен 2011 21:19 могут ли сигареты накладываться друг на друга? например: 0 0 0 2 0 1 0 3 xurshid_n Re: Clarification [1] // Задача 1469. Не курить! 8 май 2012 19:20 да Читай Кормен! (и плюс http://e-maxx.ru/algo/intersecting_segments ) ibra (TNU) Re: Clarification // Задача 1469. Не курить! 25 мар 2013 23:44 спасибо конечно за совет, но я знаю что эта задача есть и в Кормене и на емаксе. Я просто уточнял могут ли отрезки накладываться nikonoff (ONPU) yahoo // Задача 1469. Не курить! 1 дек 2008 16:39 using red-black tree for line-sweeping algorithm Todor Tsonkov What's the "good" algo for this problem [11] // Задача 1469. Не курить! 25 сен 2006 01:03 I coded for 10 minutes brute force which got TL on test 4.. any ideas about the "good" algo ? Ilya Rasenstein (Lyceum #40) Re: What's the "good" algo for this problem [10] // Задача 1469. Не курить! 25 сен 2006 21:04 Surely! std::set 4ever! Todor Tsonkov Re: What's the "good" algo for this problem [9] // Задача 1469. Не курить! 25 сен 2006 21:32 Haha :) Some more hints ;) Vladimir Yakovlev (USU) Read Cormen's "Introduction to Algorithms" (-) [8] // Задача 1469. Не курить! 25 сен 2006 23:36 Ilya Rasenstein (Lyceum #40) Re: Read Cormen's "Introduction to Algorithms" (-) [7] // Задача 1469. Не курить! 26 сен 2006 10:54 You can implement stuff, described in Cormen, easily, using set. That's what I was trying to say. Ilya Razenshteyn. Vedernikoff Sergey Re: Read Cormen's "Introduction to Algorithms" (-) [6] // Задача 1469. Не курить! 6 окт 2006 13:41 There is obvious "slide line" algo, that can be applied in O(NlogN). But there is a little problem here: perpendicular to ox line segments... EfremovAleksei Re: Read Cormen's "Introduction to Algorithms" (-) [1] // Задача 1469. Не курить! 13 ноя 2006 16:35 It's not problem! I don't exam this case and got AC. Todor Tsonkov No subject // Задача 1469. Не курить! 15 ноя 2006 14:31 Can you explain a little more about this algo ? Thunder Re: Read Cormen's "Introduction to Algorithms" (-) // Задача 1469. Не курить! 1 апр 2007 16:13 This isn't problem too. Just rotate all points by the constant angle. const angle=pi/60; var x,y,buf1,buf2:real; begin ... Buf1:=x; Buf2:=y; x:=Buf1*cos(angle)-Buf2*sin(angle); y:=Buf1*sin(angle)+Buf2*cos(angle); Edited by author 01.04.2007 16:14 svr Re: Read Cormen's "Introduction to Algorithms" (-) [2] // Задача 1469. Не курить! 13 июл 2007 17:09 I solved for me the little problem of vertical segments by applying affine matrix [2 3] [5 -7] or any other to given coordinates. As result algo from Cormen can be taken without any changes. Edited by author 13.07.2007 17:09 Lomir Re: Read Cormen's "Introduction to Algorithms" (-) [1] // Задача 1469. Не курить! 14 июл 2007 00:43 As far as me, I used some my heuristics with vertical segments: First, when reading points i makred point with lesser x cordinate as enter point. I sorted points by X, and if X are eual then sorted by enter mark. This assumes then enterpoint will be before exitpoint of segment in set. Denis Koshman Re: Read Cormen's "Introduction to Algorithms" (-) // Задача 1469. Не курить! 30 авг 2008 04:41 Vertical segments are easy to treat. Just sort X ascendingly and for equal X sort Y ascendingly. When you add vertical segment, consider its topmost Y coordinate during comparisons, and when you add some other segment, assume equality when its scan-line ordinate is compared to that one of vertical segment in the set. Such behavior is identical to the one we'd apply to the segments set after rotating it for small enough angle. Another way to see that - apply skew affine transform x2 = x+y*1e-6 y2 = y and see how formerly vertical segments are handled in this case. Edited by author 30.08.2008 04:52 Vladimir Yakovlev (USU) Problem 1469 "No smoking!" has been rejudged (+) // Задача 1469. Не курить! 22 авг 2007 20:46 New tests has been added. 7 authors have lost AC. Alias (Alexander Prudaev) WA#1 :) test #1 is sample test, isn't? [2] // Задача 1469. Не курить! 5 апр 2007 22:06 i implement sweep line algorithm, using STL set Samsonov Alex [USU] Re: WA#1 :) test #1 is sample test, isn't? [1] // Задача 1469. Не курить! 18 июл 2007 17:38 Hmmm... I also have WA-1 but my program works correct on the samples Vladimir Yakovlev (USU) First and second tests correspond to sample tests for this problem (-) // Задача 1469. Не курить! 19 июл 2007 14:29 EfremovAleksei I use Treap and have TL#15! [1] // Задача 1469. Не курить! 8 ноя 2006 13:03 I don't understand, how i can get AC! Did Anybody got Ac, using decart tree? EfremovAleksei Re: I use Treap and have TL#15! // Задача 1469. Не курить! 8 ноя 2006 13:51 I found my bug and got AC. Thanks to author for good problem! IFIT Help, I have WA 16 [1] // Задача 1469. Не курить! 18 окт 2006 11:49 I use "slide line" algorithm from "I to A", Cormen; Program works correct with vertical lines; What can be wrong- may be some tests? IFIT Re: Help, I have WA 16 // Задача 1469. Не курить! 18 окт 2006 16:16 All right, I find the problem. When i debug test on my comp with brute force method, i found that function that cross cuts in "slide line" method works incorrect ( i'll say no body where :) ). I now I have SA! Alex_SyktSU Interesting [1] // Задача 1469. Не курить! 24 сен 2006 14:44 Interesting to now, why when I write like this: int map[50001][4]; int N; cin >> N; for (int i=0; i<N; i++) { scanf("%d %d %d %d", &map[i][0], &map[i][1], &map[i][2], &map[i][3]); ... I got wa2 and when I write like this: for (int i=0; i<N; i++) { cin >> map[i][0] >> map[i][1] >> map[i][2] >> map[i][3];.. I succesfully pass second test ? Marko Tintor Re: Interesting // Задача 1469. Не курить! 10 окт 2006 02:33 don't mix cin and scanf! Fetisov Kiselev USTU_RI - RTF What the answers for this tests? [1] // Задача 1469. Не курить! 24 сен 2006 14:56 Test 2 0 0 5 0 3 0 15 0 And this test 2 0 0 5 0 3 0 3 15 Alex_SyktSU Re: What the answers for this tests? // Задача 1469. Не курить! 24 сен 2006 15:09 It seems to be YES 1 2 for both.
|