POJ 1066 Treasure Hunt [想法题]

题目链接: http://poj.org/problem?id=1066

--------------------------------------------------------------------------------------------------------

这题刚看后可能会去纠结如何建图后进行最短路

不过这样做不仅代码会复杂许多 还有可能出现些不好判断的部分

不过再多想一下我们可以发现如下性质

如果起点和终点位于某条障碍线段的两侧 那么这条线段有且仅有一次被穿过

所以只要统计起点和终点连线穿过的线段条数即可得到答案

又由于保证输入都是整数 所以我们只用在边界上枚举所有相邻整点的中点作为起点即可

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 struct node

 {

     double x, y;

 }a[], b, c;

 double cross(const node &aa, const node &bb, const node &cc)

 {

     return (bb.x - aa.x) * (cc.y - aa.y) - (bb.y - aa.y) * (cc.x - aa.x);

 }

 bool check(const node &aa, const node &bb, const node &cc, const node &dd)

 {

     return cross(aa, bb, cc) * cross(aa, bb, dd) < ;

 }

 int n, ans = , cnt;

 int main()

 {

     scanf("%d", &n);

     for(int i = ; i <= (n << ); ++i)

         scanf("%lf%lf", &a[i].x ,&a[i].y);

     scanf("%lf%lf", &b.x , &b.y);

     for(int i = ; i < ; ++i)

     {

         cnt = ;

         c.x = 0.5 + i;

         c.y = ;

         for(int j = ; j < (n << ); j += )

             if(check(a[j], a[j + ], b, c))

                 ++cnt;

         ans = min(ans, cnt);

         cnt = ;

         c.x = 0.5 + i;

         c.y = ;

         for(int j = ; j < (n << ); j += )

             if(check(a[j], a[j + ], b, c))

                 ++cnt;

         ans = min(ans, cnt);

         cnt = ;

         c.y = 0.5 + i;

         c.x = ;

         for(int j = ; j < (n << ); j += )

             if(check(a[j], a[j + ], b, c))

                 ++cnt;

         ans = min(ans, cnt);

         cnt = ;

         c.y = 0.5 + i;

         c.x = ;

         for(int j = ; j < (n << ); j += )

             if(check(a[j], a[j + ], b, c))

                 ++cnt;

         ans = min(ans, cnt);

     }

     printf("Number of doors = %d\n", ans + );

     return ;

 }