青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

POJ 1066——Treasure Hunt解題報告

我剛開始被這道題目的名字吸引了,因為它和寶藏有關,呵呵^_^不過把題目讀完以后才發現這道題是個無聊的計算幾何題 ,說實話有點失望。。。

題目的大意是這樣的:尋寶者在一個被分割成很多房間的正方形迷宮里尋寶,這個迷宮是100*100的正方形而且四個頂點坐標一定。尋寶者具有把墻鑿穿通過的能力,若尋寶者可以從正方形的任意一個邊界進入,問到達藏寶地點最少要穿過幾道墻?

這個題的解法是:枚舉每一個入口。然后在所有的情況中取穿墻數最少的輸出即可。
考察每一個入口的時候,枚舉每條邊,如果起點和終點在這條直線的兩側,那么尋寶者一定要穿過一道墻。于是此題轉化成了判斷2點是否在一條直線的異側的問題。模板解決~

由于自己寫的有點冗長,于是參考了下網上的代碼,發現將所有邊界上的點按照角度排序的確是個很巧妙的方法,學習了^_^

//coded by abilitytao
//Time:2009年8月5日17:50:19

#include
<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
double const EPS = 1e-8;
const int INF = 0xf777777;
#define zero(x) (((x)>0?(x):-(x))<eps) 



struct Point
{
    
double x,y;
    Point()
{}
       Point(
double a, double b):x(a), y(b){}
       
bool operator<(Point a){return atan2(y - 50, x - 50< atan2(a.y - 50, a.x - 50); }
}


struct Line// 定義一條線段,用起點和終點來表示 
{               
    Point a, b; 
    Line() 
{} 
    Line(Point p10, Point p20): a(p10), b(p20) 
{} //Line a(p1,p2);
}



Point mypoint[
64], s, t;
Line myline[
30];
int n, countnum, minnum;

double xmult(Point p1, Point p2 , Point p0)
{
    
return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}

int same_side(Point p1,Point p2,Line l)

    
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>EPS; 
}


int main()
{
    
int i, j, ans;
    minnum 
= INF; countnum = 0;
    mypoint[countnum
++= Point(00);
    mypoint[countnum
++= Point(1000);
    mypoint[countnum
++= Point(0100);
    mypoint[countnum
++= Point(100100);
    
    cin 
>> n;
    
for(i = 0; i < n; i++)
    
{
        scanf(
"%lf%lf%lf%lf",&myline[i].a.x ,&myline[i].a.y ,&myline[i].b.x ,&myline[i].b.y);
        mypoint[countnum
++= myline[i].a;
        mypoint[countnum
++= myline[i].b;
    }

    scanf(
"%lf%lf",&s.x,&s.y);
    
       sort(mypoint, mypoint
+countnum);
       
       
for(i=0;i<countnum;i++ )
       
{
           ans 
= 0;
           t 
= Point( (mypoint[i].x + mypoint[(i+1)%countnum].x)/2, (mypoint[i].y + mypoint[(i+1)%countnum].y)/2 );
           
for(j = 0; j < n; j++)          
               
if(!same_side(s, t, myline[j]))
                   ans
++;
            
if(ans <minnum) minnum = ans;
       }

       
       printf(
"Number of doors = %d\n", minnum+1);
       
return 0;
}

posted on 2009-08-05 23:58 abilitytao 閱讀(1572) 評論(0)  編輯 收藏 引用

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产午夜精品全部视频播放 | 性欧美video另类hd性玩具| 免费日韩成人| 欧美激情区在线播放| 亚洲精品一二| 在线亚洲伦理| 国产三级精品三级| 女同性一区二区三区人了人一 | 亚洲第一福利视频| 久热爱精品视频线路一| 久久一区二区三区四区| 亚洲欧洲在线一区| 亚洲免费观看高清在线观看 | 久久久久久香蕉网| 日韩亚洲一区二区| 国产视频亚洲精品| 亚洲成人在线网| 亚洲国产女人aaa毛片在线| 欧美激情一区二区三区四区| 在线一区二区三区四区五区| 欧美一级在线播放| 亚洲日本va在线观看| 99精品视频免费在线观看| 欧美不卡视频一区| 麻豆久久婷婷| 欧美激情综合色综合啪啪| 中国成人黄色视屏| 久久精品女人| 亚洲一区二区三区在线播放| 久久精品国产99国产精品| 亚洲美女在线一区| 欧美一区二区三区四区在线观看地址| 亚洲人成啪啪网站| 亚洲欧美精品| 国产精品99久久久久久www| 久久精品中文| 午夜精品区一区二区三| 免费日韩精品中文字幕视频在线| 亚洲欧美一区二区三区在线| 免费成人黄色av| 久久久久国产精品一区三寸| 国产精品久久国产精麻豆99网站| 欧美不卡视频一区发布| 国产视频精品网| 99热免费精品| 日韩亚洲视频| 免费日韩一区二区| 欧美成人国产va精品日本一级| 国产精品视频免费观看| 亚洲激情视频在线| 亚洲第一天堂av| 久久精品官网| 久久久综合视频| 国产亚洲成人一区| 午夜精品久久久久| 香蕉久久夜色精品国产使用方法| 欧美日韩视频| 亚洲最新视频在线| 夜夜躁日日躁狠狠久久88av| 欧美国产先锋| 亚洲人成网在线播放| 亚洲日本精品国产第一区| 久久久久久久久伊人| 另类av一区二区| 亚洲国产精品国自产拍av秋霞| 久久久水蜜桃| 欧美激情亚洲精品| 亚洲人成网站999久久久综合| 久久亚洲精品视频| 欧美成人网在线| 亚洲国产婷婷综合在线精品 | 久久成人免费| 狠狠色狠狠色综合日日小说| 久久久久久久高潮| 欧美成年视频| 一本一本大道香蕉久在线精品| 欧美激情影音先锋| 亚洲尤物视频在线| 日韩视频一区二区在线观看 | 亚洲欧美中文日韩v在线观看| 国产精品国产三级国产普通话99| 亚洲无线观看| 蜜桃久久av一区| 亚洲人人精品| 国产精品卡一卡二| 久久精品官网| 99精品国产在热久久| 欧美一区二区三区电影在线观看| 国产麻豆视频精品| 巨乳诱惑日韩免费av| 日韩视频一区二区三区| 久久精品一区蜜桃臀影院 | 国产精品麻豆欧美日韩ww| 午夜精品视频网站| 亚洲第一精品电影| 亚洲欧美日韩系列| 亚洲成人直播| 国产精品乱看| 欧美不卡福利| 亚洲视频精品在线| 欧美超级免费视 在线| 国产精品99久久久久久宅男 | 国产欧美日韩激情| 欧美va日韩va| 欧美一区二区三区四区在线| 亚洲国产美女精品久久久久∴| 久久不见久久见免费视频1| 亚洲人成在线播放网站岛国| 国产精品日韩久久久久| 欧美a级一区二区| 亚洲欧美日韩第一区| 亚洲国产cao| 久久综合九色综合久99| 一区二区三区视频免费在线观看 | 国产精品嫩草99av在线| 欧美福利一区| 久久大逼视频| 亚洲与欧洲av电影| 亚洲美女在线看| 欧美激情一区二区久久久| 欧美专区日韩专区| 亚洲一区999| 夜夜嗨av一区二区三区中文字幕 | 久久久免费精品视频| 亚洲一区二区三区三| 日韩视频不卡| 亚洲欧洲精品一区二区三区波多野1战4 | 老司机精品导航| 久久精品国产精品亚洲| 亚洲在线观看免费| 亚洲一区二区欧美日韩| 日韩午夜一区| 亚洲久久一区二区| 亚洲高清二区| 亚洲激情av在线| 亚洲激情视频在线| 亚洲福利视频二区| 精品成人一区二区三区| 老司机午夜精品视频| 亚洲一区二区三区视频播放| 日韩一二在线观看| 日韩视频一区| 亚洲人成在线播放网站岛国| 在线日韩成人| 亚洲区国产区| 99视频国产精品免费观看| 日韩视频精品在线| 一区二区三区高清视频在线观看| 亚洲精一区二区三区| 一本色道久久| 香蕉久久一区二区不卡无毒影院 | 在线观看一区二区视频| 在线电影欧美日韩一区二区私密| 今天的高清视频免费播放成人| 国产一区二区三区黄| 永久久久久久| 亚洲免费高清视频| 亚洲欧美国产精品专区久久| 欧美一级电影久久| 久久手机免费观看| 亚洲高清自拍| 亚洲性夜色噜噜噜7777| 午夜精品久久久久影视| 久久精品九九| 欧美激情网友自拍| 国产精品捆绑调教| **欧美日韩vr在线| 亚洲色无码播放| 久久蜜桃资源一区二区老牛 | 亚洲黄色一区| 亚洲综合精品| 久久婷婷综合激情| 欧美日韩色婷婷| 激情丁香综合| 一区二区日本视频| 久久久久久9999| 最近中文字幕mv在线一区二区三区四区| 99精品国产高清一区二区| 午夜欧美大尺度福利影院在线看| 久久视频一区二区| 欧美日韩综合在线| 伊人久久亚洲影院| 亚洲午夜羞羞片| 美国成人直播| 亚洲午夜精品福利| 麻豆freexxxx性91精品| 国产精品久久久久久模特| 亚洲二区在线| 欧美影视一区| 日韩视频欧美视频| 久久香蕉国产线看观看网| 国产精品v欧美精品v日本精品动漫 | 久久久视频精品| 国产欧美日韩另类一区| 亚洲最新中文字幕| 乱人伦精品视频在线观看| 亚洲天堂网在线观看| 麻豆精品视频在线观看| 国产视频精品免费播放| 亚洲综合二区|