牛客练习赛65 C 二维动点

二维动点

https://ac.nowcoder.com/acm/contest/5961/C

C 二维动点

题目地址：

https://ac.nowcoder.com/acm/contest/5961/C

基本思路：

这道题难点在分类讨论和细节，特别注意这句话"选择一个不和当前所在位置重叠的点"。

那么考虑一下答案有几种可能，并且分别会在什么情况出现：

(1).首先如果终点就是 $(0,0)$ 那么很明显答案就是 $0$ ;

(2).如果终点在其中一个点和起点的连线上那么明显移动 $1$ 次就能到达，这个情况我们用 $map$ 直接记录斜率就行了，记住不要记浮点数，除 $gcd$ 记录最简分数的 $pair$ ，防止丢精度。

(3). 然后如果存在两个点，这两个点中的一个和起点的连线，和另一个点和终点的连线相交，那么我们到达交点，然后从这个交点位置就能抵达终点也就是移动 $2$ 次。我们观察并且多次尝试就会发现，只要点的数量大于 $2$ 并且不满足(1)(2)，就会一定出现这种相交，这时我们直接输出 $2$ 。

(4). 然后如果不存在这样两条相交线，那么也就是样例中第一个查询的情况，这个时候我们只要开始随意跳一次就能出现相交情况了，所以总体移动次数是 $3$ 次。考虑一下这个情况什么时候会出现，联系样例我们发现其实就是 $n = 2$ ，并且出现平行四边形的情况(好像可以快速判平行四边形，我这里是暴力计算的)，所以 $n = 2$ 时是平行四边则输出 $3$ 否者 $2$ 。

(5). 最后我们考虑一下没有答案的情况，也就是 $-1$ 的情况，开始我认为这个情况只会在 $n = 1$ 时出现，因为如果很多点在和起点的一条直线上，只要不满足(1)(2)，也是如(3)一样有相交，但这时候的交点却会是其中一个点本身，根据开头说的特别注意的那句话我们能明显发现是不符的，因此是斜率小于一种(小于 $1$ 的情况就是不存在有效点)时答案为 $-1$ 。

(6). 最后还是由于特别注意里的那句话，如果输入里有 $(0,0)$ 点，那么我们要直接忽略这个点，也就是当它不存在。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

inline int gcd(int a,int b) {
  return b == 0 ? a : gcd(b,a % b);
}
const double eps = 1e-8;
int sgn(double x) {
  if (x > eps)
    return 1;
  if (x < -eps)
    return -1;
  return 0;
}

const int maxn = 1e5 + 10;
int n,q,x,y;
map<pii,int> memo;
pii pt[maxn];
signed main() {
  IO;
  memo.clear();
  cin >> n >> q;
  rep(i, 1, n) {
    cin >> x >> y;
    pt[i].first = x, pt[i].second = y;
    //(0,0) 直接忽略;
    if (x == 0 && y == 0) { i--; n--; continue; }
    //存最简分数，不会卡精度;
    if (y < 0) y = -y, x = -x;
    int p = gcd(abs(x), abs(y));
    memo[{x / p, y / p}]++;
  }
  while (q--) {
    cin >> x >> y;
    if (x == 0 && y == 0) {//(0,0)答案为0;
      cout << 0 << '\n';
      continue;
    }
    int mx = x, my = y;
    if (y < 0) y = -y, x = -x;
    int p = gcd(abs(x), abs(y));
    x /= p, y /= p;
    if (memo.count({x, y})) {// 在一条线上,一次能到达;
      cout << 1 << '\n';
      continue;
    }
    if (memo.size() <= 1) { // 小于一种斜率且不符合上面的情况;
      cout << -1 << '\n';
      continue;
    }
    if (n > 2) { // 这时候一定有相交,所以答案为2;
      cout << 2 << '\n';
      continue;
    }
    //这部分是暴力判断平行四边形，好像复杂了;
    bool v = true;
    double k1 = (double) pt[1].second / (double) pt[1].first;
    double k2 = (double) (my - pt[2].second) / (double) (mx - pt[2].first);
    if (sgn(k1 - k2) != 0) v = false;
    k1 = (double) pt[2].second / (double) pt[2].first;
    k2 = (double) (my - pt[1].second) / (double) (mx - pt[1].first);
    if (sgn(k1 - k2) != 0) v = false;
    if (v) cout << 3 << '\n';
    else cout << 2 << '\n';
  }
  return 0;
}