[57]射击游戏-网易2018秋

1.题目描述

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(0,0),平面上有n只怪物,每个怪物有所在的坐标(x[i], y[i])。小易进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。
小易是这个游戏的VIP玩家,他拥有两项特权操作:

1. 让平面内的所有怪物同时向任意同一方向移动任意同一距离
2. 让平面内的所有怪物同时对于小易(0,0)旋转任意同一角度

小易要进行一次射击。小易在进行射击前,可以使用这两项特权操作任意次。
小易想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮小易。

• 如样例所示:

所有点对于坐标原点(0,0)顺时针或者逆时针旋转45°,可以让所有点都在坐标轴上,所以5个怪物都可以消灭。

• 输入描述:
  输入包括三行。
  第一行中有一个正整数n(1≤n≤50),表示平面内的怪物数量。
  第二行包括n个整数x[i](-1,000,000≤x[i]≤1,000,000),表示每只怪物所在坐标的横坐标,以空格分割。
  第二行包括n个整数y[i](-1,000,000≤y[i]≤1,000,000),表示每只怪物所在坐标的纵坐标,以空格分割。
• 输出描述:
  输出一个整数表示小易最多能消灭多少只怪物。
• 输入例子 1:

  5
  0 -1 1 1 -1
  0 -1 -1 1 1
  

• 输出例子 1:

  5
  

2.题目解析

两点必共线，三点必垂直共线两点所在直线。

关系	表示	向量关系式	坐标关系式
平行		()
垂直	(,)

3.参考答案

#include <bits/stdc++.h>
using namespace std;
int solve(int* x,int* y,int n) {
  if (n <= 3) return n; // 两点必共线，三点必垂直共线两点所在直线
  int res = 1;
  for (int i = 0; i < n; i++) { // 第一个点
    for (int j = i+1; j < n; j++) { // 第二个点
      int dx1 = x[j] - x[i];
      int dy1 = y[j] - y[i];
      for (int k = j+1; k < n; k++) { // 第三点
        int cnt = 3;
        for (int r = k+1; r < n; r++) { // 第四点
          if(r == i|| r == j||r == k) continue; // 除去重复点
          int dx2 = x[r] - x[i];
          int dy2 = y[r] - y[i];
          if (dy1 * dx2 ==  dy2 * dx1){ // 判断i、j、r是否在共线
            cnt++;
          }else {
            int dx3 = x[r] - x[k];
            int dy3 = y[r] - y[k];
            if (dy1 * dy3 == -dx3 * dx1){ // 判断i、j与k、r是否垂直
              cnt++;
            }
          } 
        }
        res = max(res, cnt);
      }
    }
  }
  return res;
}
int main() {
  int n = 0;
  scanf("%d",&n);
  int x[n],y[n];
  for (int i = 0; i < n; i++)
    scanf("%d",&x[i]);
  for (int i = 0; i < n; i++)
    scanf("%d",&y[i]);
  printf("%d\n",solve(x,y,n));
}

上面的代码只能通过90%，为什么？
因为没有考虑这种情况

4
0 1 2 0
0 0 0 1

这种情况第三点和第四点向量垂直于第一点第二点向量没有统计，所以r需要从头遍历。

#include <bits/stdc++.h>
using namespace std;
int solve(int* x,int* y,int n) {
  if (n <= 3) return n; // 两点必共线，三点必垂直共线两点所在直线
  int res = 1;
  for (int i = 0; i < n; i++) { // 第一个点
    for (int j = i+1; j < n; j++) { // 第二个点
      int dx1 = x[j] - x[i];
      int dy1 = y[j] - y[i];
      for (int k = j+1; k < n; k++) { // 第三点
        int cnt = 3;
        for (int r = 0; r < n; r++) { // 第四点
          if(r == i|| r == j||r == k) continue; // 除去重复点
          int dx2 = x[r] - x[i];
          int dy2 = y[r] - y[i];
          if (dy1 * dx2 ==  dy2 * dx1){ // 判断i、j、r是否在共线
            cnt++;
          }else {
            int dx3 = x[r] - x[k];
            int dy3 = y[r] - y[k];
            if (dy1 * dy3 == -dx3 * dx1){ // 判断i、j与k、r是否垂直
              cnt++;
            }
          } 
        }
        res = max(res, cnt);
      }
    }
  }
  return res;
}
int main() {
  int n = 0;
  scanf("%d",&n);
  int x[n],y[n];
  for (int i = 0; i < n; i++)
    scanf("%d",&x[i]);
  for (int i = 0; i < n; i++)
    scanf("%d",&y[i]);
  printf("%d\n",solve(x,y,n));
}

可以把if(r == i|| r == j||r == k) continue;去掉，把int cnt = 3;改成int cnt = 0;

#include <bits/stdc++.h>
using namespace std;
int solve(int* x,int* y,int n) {
  if (n <= 3) return n; // 两点必共线，三点必垂直共线两点所在直线
  int res = 1;
  for (int i = 0; i < n; i++) { // 第一个点
    for (int j = i+1; j < n; j++) { // 第二个点
      int dx1 = x[j] - x[i];
      int dy1 = y[j] - y[i];
      for (int k = j+1; k < n; k++) { // 第三点
        int cnt = 0;
        for (int r = 0; r < n; r++) { // 第四点
          int dx2 = x[r] - x[i];
          int dy2 = y[r] - y[i];
          if (dy1 * dx2 ==  dy2 * dx1){ // 判断i、j、r是否在共线
            cnt++;
          }else {
            int dx3 = x[r] - x[k];
            int dy3 = y[r] - y[k];
            if (dy1 * dy3 == -dx3 * dx1){ // 判断i、j与k、r是否垂直
              cnt++;
            }
          } 
        }
        res = max(res, cnt);
      }
    }
  }
  return res;
}
int main() {
  int n = 0;
  scanf("%d",&n);
  int x[n],y[n];
  for (int i = 0; i < n; i++)
    scanf("%d",&x[i]);
  for (int i = 0; i < n; i++)
    scanf("%d",&y[i]);
  printf("%d\n",solve(x,y,n));
}

牛客题目