• <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.

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

            #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會超時。。。
                            }

                        }

                    }

                    
            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 閱讀(620) 評論(0)  編輯 收藏 引用 所屬分類: 計算幾何POJ
            国产精品免费久久久久影院| 国产精品成人久久久久三级午夜电影| 久久久这里有精品| 精品久久久久久国产| 精品久久久久久亚洲| 国产成人AV综合久久| 久久精品一区二区三区AV| 久久国产一区二区| 一级做a爰片久久毛片毛片| 久久精品国内一区二区三区| 亚洲乱码日产精品a级毛片久久 | 久久综合狠狠综合久久综合88| 精品一区二区久久| 亚洲精品国产美女久久久| 亚洲国产成人久久精品动漫| 亚洲国产精品无码成人片久久| 亚洲国产成人久久精品影视 | 一97日本道伊人久久综合影院 | 久久精品国产亚洲AV忘忧草18| 久久香蕉一级毛片| 天天躁日日躁狠狠久久| 久久只有这里有精品4| 国产精品熟女福利久久AV| 久久综合给合久久狠狠狠97色69| 中文字幕无码久久人妻| 久久精品国产一区二区| 国产69精品久久久久99尤物 | 久久伊人五月丁香狠狠色| 久久精品国产欧美日韩| 精品久久久久久无码人妻蜜桃| 久久精品无码一区二区三区| 99久久人妻无码精品系列| 精品少妇人妻av无码久久| 久久精品人人槡人妻人人玩AV| 久久99国产综合精品免费| 无码伊人66久久大杳蕉网站谷歌| 亚洲中文字幕久久精品无码喷水 | 亚洲а∨天堂久久精品9966| 久久成人18免费网站| 中文字幕精品久久久久人妻| 一本一道久久综合狠狠老|