• <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
            91精品国产高清久久久久久io| 久久免费精品视频| 久久国产精品免费一区| 久久伊人亚洲AV无码网站| 伊色综合久久之综合久久| 久久这里的只有是精品23| 亚洲AV无码久久精品蜜桃| 一本色道久久88加勒比—综合| 久久露脸国产精品| 少妇高潮惨叫久久久久久| 久久综合狠狠综合久久激情 | 国产精品久久久久影视不卡| 久久er国产精品免费观看8| 噜噜噜色噜噜噜久久| 亚洲一区二区三区日本久久九| 亚洲精品乱码久久久久久蜜桃| 久久精品亚洲一区二区三区浴池| 久久久久亚洲AV无码专区桃色| 亚洲午夜久久久久妓女影院 | 成人国内精品久久久久影院VR| 噜噜噜色噜噜噜久久| 国产精品久久久久久久午夜片| 久久久久高潮毛片免费全部播放| 无码任你躁久久久久久老妇| 久久不射电影网| 久久亚洲中文字幕精品有坂深雪 | 久久精品国产亚洲av瑜伽| 97r久久精品国产99国产精| 精品一二三区久久aaa片| 久久国产精品视频| 9191精品国产免费久久| 国产精品久久久久久影院| 久久久久久国产精品免费无码| 久久无码AV一区二区三区| 亚洲国产成人久久综合区| 久久国产午夜精品一区二区三区| 精品人妻久久久久久888| 国产69精品久久久久777| 久久精品亚洲一区二区三区浴池 | 亚洲国产天堂久久综合网站| 国产午夜免费高清久久影院|