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

            我希望你是我獨家記憶

            一段永遠封存的記憶,隨風而去
            posts - 263, comments - 31, trackbacks - 0, articles - 3
               :: 首頁 :: 新隨筆 ::  :: 聚合  :: 管理

            F1120——計算幾何——多邊形內點

            Posted on 2008-09-02 20:09 Hero 閱讀(252) 評論(0)  編輯 收藏 引用 所屬分類: 代碼如詩--ACM
             1 //Accepted 1120 C++ 0.02s 190K 054100526 FZU
             2 
             3 //點在多邊形內
             4 //不滿足 z=px+qy 的個數為(p-1)*(q-1)/2
             5 
             6 #include <stdio.h>
             7 #include <stdlib.h>
             8 #include <string.h>
             9 
            10 #define offset 10000
            11 #define eps 1e-8
            12 #define zero(x) (((x)>0?(x):-(x))<eps)
            13 #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
            14 const int INF = 99999999 ;
            15 const int size = 20 ;
            16 
            17 struct point
            18 {
            19     double x ;
            20     double y ;
            21 };
            22 struct point pt[size] ;
            23 
            24 double minx, miny ;
            25 double maxx, maxy ;
            26 int inn ; int inp, inq ; int ct ;
            27 
            28 void input() 
            29 {
            30     minx = miny = INF ;    maxx = maxy = -1*INF ;
            31     forint i=0; i<inn; i++ )
            32     {
            33         scanf( "%lf %lf"&pt[i].x, &pt[i].y ) ;
            34         //if( minx > pt[i].x ) minx = pt[i].x ;
            35         //if( miny > pt[i].y ) miny = pt[i].y ;
            36 
            37         //if( maxx < pt[i].x ) maxx = pt[i].x ;
            38         //if( maxy < pt[i].x ) maxy = pt[i].y ;
            39     }    
            40 }
            41 
            42 double xmult(point p1,point p2,point p0){
            43     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
            44 }
            45 
            46 //判點在任意多邊形內,頂點按順時針或逆時針給出
            47 //on_edge表示點在多邊形邊上時的返回值,offset為多邊形坐標上限
            48 int inside_polygon(point q,int n,point* p,int on_edge=1){
            49     point q2;
            50     int i=0,count;
            51     while (i<n)
            52         for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++)
            53             if (zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps)
            54                 return on_edge;
            55             else if (zero(xmult(q,q2,p[i])))
            56                 break;
            57             else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)
            58                 count++;
            59     return count&1;
            60 }
            61 
            62 void process()
            63 {
            64     scanf( "%d %d"&inp, &inq ) ;
            65 
            66     struct point q ; q.x = 0.0 ; q.y = 0.0 ;
            67 
            68     if( inside_polygon( q, inn, pt, 1 ) )
            69     {
            70         printf( "The pilot is in danger!\n" ) ;
            71         printf( "The secret number is %d.\n", (inp-1)*(inq-1)/2 ) ;
            72     }
            73     else
            74     {
            75         printf( "The pilot is safe.\n" ) ;
            76     }
            77     printf( "\n" ) ;
            78 }
            79 
            80 int main()
            81 {
            82     //freopen( "in.txt", "r", stdin ) ;
            83 
            84     ct = 1 ;
            85     while( scanf( "%d"&inn ) != EOF && inn )
            86     {
            87         printf( "Pilot %d\n", ct++ ) ;
            88 
            89         input() ;
            90 
            91         process() ;
            92 
            93         //output() ;
            94     }
            95 
            96     return 0 ;
            97 }
            精品国产一区二区三区久久久狼 | 伊人久久大香线蕉综合Av| 人人狠狠综合88综合久久| 人人妻久久人人澡人人爽人人精品| 亚洲综合熟女久久久30p| 免费观看久久精彩视频 | 久久久久久久久无码精品亚洲日韩| 久久精品国产一区| 7777久久久国产精品消防器材| AAA级久久久精品无码区| 久久久久亚洲精品天堂| 亚洲国产成人久久综合碰| 日韩亚洲欧美久久久www综合网| 99久久国产精品免费一区二区| 国产午夜精品久久久久九九| 久久久久AV综合网成人| 少妇人妻综合久久中文字幕| 国产香蕉97碰碰久久人人| 精品久久一区二区三区| 久久久老熟女一区二区三区| 欧美亚洲国产精品久久久久| 国产精品无码久久四虎| 91久久福利国产成人精品| 久久国产精品一区二区| 久久久久人妻精品一区| 亚洲精品无码久久一线| 精品伊人久久大线蕉色首页| 亚洲欧洲中文日韩久久AV乱码| 久久夜色精品国产亚洲av| 久久av高潮av无码av喷吹| 国产精品99久久久久久宅男| 久久99精品久久久久久野外| 国产伊人久久| 国产精品久久新婚兰兰| 久久人人爽人人爽人人片AV麻烦| 大香伊人久久精品一区二区| 久久久精品国产| 无码超乳爆乳中文字幕久久| 亚洲AV日韩精品久久久久久 | 国産精品久久久久久久| 日本欧美国产精品第一页久久|