• <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
            精品国产乱码久久久久久郑州公司 | 中文字幕热久久久久久久| 久久久精品波多野结衣| 久久无码人妻精品一区二区三区| 国产综合精品久久亚洲| 2021国产精品久久精品| 久久99国内精品自在现线| 久久精品女人天堂AV麻| 一本久久a久久精品亚洲| 久久se精品一区二区| 香蕉aa三级久久毛片| 996久久国产精品线观看| 久久综合伊人77777| 久久精品中文闷骚内射| 欧美精品丝袜久久久中文字幕| 久久久久高潮毛片免费全部播放 | 奇米综合四色77777久久| 中文精品久久久久国产网址| 2021国产精品久久精品| 99国内精品久久久久久久| 亚洲AV日韩AV天堂久久| 精品国产91久久久久久久a| 嫩草伊人久久精品少妇AV| 老司机午夜网站国内精品久久久久久久久| 日韩人妻无码一区二区三区久久99| 亚洲国产天堂久久久久久| 久久精品国产亚洲综合色| 亚洲国产综合久久天堂| 久久亚洲色一区二区三区| 青青草原1769久久免费播放| 久久久无码精品亚洲日韩按摩| 亚洲欧洲精品成人久久曰影片| 青青国产成人久久91网| 国内精品久久国产大陆| 久久精品a亚洲国产v高清不卡| 久久久久久精品免费免费自慰| 婷婷国产天堂久久综合五月| 久久久久久国产a免费观看黄色大片| 人人狠狠综合久久亚洲高清| 精品人妻伦九区久久AAA片69| 成人亚洲欧美久久久久|