题目链接: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 ;
}