• <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 閱讀(618) 評論(0)  編輯 收藏 引用 所屬分類: 計(jì)算幾何POJ
            亚洲精品成人久久久| 无码精品久久一区二区三区| 777米奇久久最新地址| 久久夜色tv网站| 久久成人国产精品二三区| 亚洲精品99久久久久中文字幕| 2021久久国自产拍精品| 日韩电影久久久被窝网| 色综合久久中文综合网| 97精品依人久久久大香线蕉97 | 久久99国产综合精品| 久久综合亚洲色一区二区三区| 国产精品热久久毛片| 久久精品国产亚洲av瑜伽| 一本色道久久88加勒比—综合| 久久99国产精品99久久| 久久99精品久久久久久噜噜 | 人妻精品久久久久中文字幕69| 久久久久噜噜噜亚洲熟女综合 | 一本综合久久国产二区| 久久成人精品视频| 亚洲午夜久久久久妓女影院| 国内精品免费久久影院| 久久精品国产秦先生| 亚洲午夜久久久久妓女影院 | 国产激情久久久久影院小草 | 91久久精品国产91性色也| 国产偷久久久精品专区| 亚洲精品美女久久久久99| 久久www免费人成精品香蕉| 久久久久人妻精品一区二区三区| 日韩AV无码久久一区二区 | 午夜精品久久久久久99热| 亚洲嫩草影院久久精品| 国产成人精品综合久久久久 | 国产精品亚洲美女久久久| 久久久久亚洲AV无码永不| 久久亚洲精品国产精品| 无码专区久久综合久中文字幕 | 久久久精品2019免费观看| 99精品久久精品|