• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            Pick-up sticks
            Time Limit: 3000MS Memory Limit: 65536K
            Total Submissions: 4189 Accepted: 1501

            Description

            Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.                                                             
                                                                                                                                                                                                  

            Input

            Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

            Output

            For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

            The picture to the right below illustrates the first case from input.

            Sample Input

            5
            1 1 4 2
            2 3 3 1
            1 -2.0 8 4
            1 4 8 2
            3 3 6 -2.0
            3
            0 0 1 1
            1 0 2 1
            2 0 3 1
            0
            

            Sample Output

            Top sticks: 2, 4, 5.
            Top sticks: 1, 2, 3.
            

            Hint

            Huge input,scanf is recommended.

            /***********************************
            暴力就行,從第一個(gè)開(kāi)始判斷
            如果兩條線段相交就把前面一條篩選掉
            判斷線段相交直接貼的吉大模板。。。
            **********************************
            */

            #include 
            <iostream>
            #include 
            <cstdio>
            #include 
            <cstring>

            using namespace std;

            const int maxn = 100000 + 5;
            const double eps=1e-10;

            struct point double x, y; };

            point p[maxn], b[maxn];
            bool ans[maxn];

            double min(double a, double b) return a < b ? a : b; }

            double max(double a, double b) return a > b ? a : b; }

            bool inter(point a, point b, point c, point d)
            {
                
            if( min(a.x, b.x) > max(c.x, d.x) ||
                    min(a.y, b.y) 
            > max(c.y, d.y) ||
                    min(c.x, d.x) 
            > max(a.x, b.x) ||
                    min(c.y, d.y) 
            > max(a.y, b.y) )
                
            return 0;

                
            double h, i, j, k;

                h 
            = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
                i 
            = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
                j 
            = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
                k 
            = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);

                
            return h * i <= eps && j * k <= eps;
            }


            int main()
            {
                
            int n;
                
            int res[maxn];
                
            while( cin >> n, n )
                
            {
                    memset( ans, 
            0sizeof( ans ) );
                    
            forint i = 0; i < n; i++ )
                    
            {
                        cin 
            >> p[i].x >> p[i].y >> b[i].x >> b[i].y;
                    }


                    
            forint i = 0; i < n; i++ )
                    
            {
                        
            forint j = i + 1; j < n; j++ )
                        
            {
                            
            if( inter(p[i], b[i], p[j], b[j] ) )
                            
            {
                                ans[i] 
            = 1;
                                
            break;              //不加break會(huì)超時(shí)。。。
                            }

                        }

                    }

                    
            int ct = 0;
                    cout 
            << "Top sticks: ";
                    
            forint i = 0; i < n; i++ )
                        
            if!ans[i] )  res[ct++= i + 1;
                    
            forint i = 0; i < ct - 1; i++ )
                        cout 
            << res[i] << "";
                    cout 
            << res[ct-1<< "." << endl;
                }

                
            return 0;
            }

            posted on 2010-10-03 16:21 Vontroy 閱讀(619) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 計(jì)算幾何POJ
            97久久精品人人澡人人爽| 青青草国产精品久久久久| 欧美亚洲另类久久综合| 亚洲国产精品久久久久网站| 99久久精品免费看国产| 欧美成a人片免费看久久| 99久久国产宗和精品1上映| 久久综合综合久久综合| 精品无码久久久久久国产| 国产毛片欧美毛片久久久| 久久久久久久国产免费看| 囯产精品久久久久久久久蜜桃 | 国产精品久久精品| 欧美日韩中文字幕久久久不卡| 久久人妻少妇嫩草AV无码专区| 国产精品午夜久久| 国产精品美女久久久m| 久久福利资源国产精品999| 久久久久久免费一区二区三区| 欧洲国产伦久久久久久久| 久久九九青青国产精品| 久久久久久亚洲Av无码精品专口| 国产精品狼人久久久久影院| 久久久久亚洲精品天堂| 久久伊人精品一区二区三区| 久久久久亚洲爆乳少妇无| 丰满少妇人妻久久久久久4| 久久精品国产亚洲AV无码麻豆 | 狠狠色婷婷久久一区二区三区| 亚洲国产成人久久综合区| 91精品观看91久久久久久 | 久久久亚洲AV波多野结衣| 久久国产免费直播| 久久久久国产日韩精品网站 | 久久嫩草影院免费看夜色| 久久精品亚洲日本波多野结衣 | 久久偷看各类wc女厕嘘嘘| 无码伊人66久久大杳蕉网站谷歌| 天堂久久天堂AV色综合| 亚洲va中文字幕无码久久 | 久久精品成人影院|