codeforces 514B. Han Solo and Lazer Gun 解题报告

题目链接：http://codeforces.com/problemset/problem/514/B

题目意思：给出双头枪的位置（x0, y0），以及 n 个突击队成员的坐标。双头枪射击一次，可以把它对住的方向（是直线，不是射线，因为是双头嘛）所有的人射杀掉。问将所有突击队成员消灭的最少射击数是多少。

首先要清楚的是，双头枪可以瞄准的方向是无限的，所以通过枚举所有方向是不现实的！方向其实就是对应斜率，但是没有理由把函数求出然后将士兵的位置一个一个代入来做吧～～～所以呢，直接求 k 就可以了，k 表示枪（x0, y0）和任意士兵（x, y）的斜率。即 k =（y - y0）/ （x - x0）

做的过程中要注意两个问题。（1）k 有可能除不尽，所以要用 double 来保存。（2）x - x0 有可能等于0，除数不能为 0 的！！但是也属于可行的一个方向，要单独判断，统计到答案中的其中一个解里。保存完所有 k 之后，去重后统计有多少个不同的 k 就是问题答案了。

　　其实还有一个地方有点疑问，就是浮点数比较。本来打算用精度控制，毕竟比较的时候用 “ = ”多少是有一点误差的，但居然过了，可能数据比较弱吧，这个不太清楚，希望有能之士可以指点指点，不胜感激 [^__^]

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 double k[maxn];

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int n;

     int x0, y0, x, y;

     while (scanf("%d%d%d", &n, &x0, &y0) != EOF) {

         int cnt = ;

         int f = ;

         int ans = ;

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

             scanf("%d%d", &x, &y);

             double tx = x - x0;

             double ty = y - y0;

             if (tx ==  && !f) {

                 ans++;

                 f = ;

             }

             else if (tx != )

                 k[cnt++] = ty / tx;     // 注意 cnt 不一定等于 n

         }

         sort(k, k+cnt);

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

             while (k[i] == k[i+] && i < cnt)

                 i++;

             ans++;

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

codeforces 514B. Han Solo and Lazer Gun 解题报告

最新文章

热门文章