What the output of? 2 0 0 1 1 1 1 2 2 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. могут ли сигареты накладываться друг на друга? например: 0 0 0 2 0 1 0 3 спасибо конечно за совет, но я знаю что эта задача есть и в Кормене и на емаксе. Я просто уточнял могут ли отрезки накладываться using redblack tree for linesweeping algorithm I coded for 10 minutes brute force which got TL on test 4.. any ideas about the "good" algo ? Surely! std::set 4ever! Haha :) Some more hints ;) You can implement stuff, described in Cormen, easily, using set. That's what I was trying to say. Ilya Razenshteyn. 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... It's not problem! I don't exam this case and got AC.
Can you explain a little more about this algo ? 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 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 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. 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 scanline 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*1e6 y2 = y and see how formerly vertical segments are handled in this case. Edited by author 30.08.2008 04:52 New tests has been added. 7 authors have lost AC. i implement sweep line algorithm, using STL set Hmmm... I also have WA1 but my program works correct on the samples I don't understand, how i can get AC! Did Anybody got Ac, using decart tree? I found my bug and got AC. Thanks to author for good problem! I use "slide line" algorithm from "I to A", Cormen; Program works correct with vertical lines; What can be wrong may be some tests? 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! 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 ? Test 2 0 0 5 0 3 0 15 0 And this test 2 0 0 5 0 3 0 3 15 It seems to be YES 1 2 for both. 
