首页 > 试题广场 >

射击游戏

[编程题]射击游戏

热度指数：2799 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(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

输出

算法知识视频讲解

littlebee

四个for循环。每个for循环选取一个点（判断该点不同于前面的点），前三个点要求不共线。

前两个点A,B通过第一条直线；

第三个点C通过另一条直线；

第四个for循环，对于剩下的n-3个点，判断是否落在这两条直线上。如果有AD与AB平行，则落在第一条直线上；如果有CD与AB垂直，则落在第二条直线上。

第四个for循环结束，可以知道这两条直线能穿过最多几个点，每次更新最大值。

所有循环结束，输出最终的最大值即可。

计算斜率来判断平行和垂直，即dx1 * dy2 == dy1 *dx2。

发表于 2017-09-10 20:50:12 回复(12)

越努力-越幸运

根据楼上说的四个for循环思路写的代码，已通过

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x[] = new int[n];
        int y[] = new int[n];
        for (int i = 0; i < n; i++)
            x[i] = scan.nextInt();
        for (int i = 0; i < n; i++)
            y[i] = scan.nextInt();
        scan.close();
        int maxShoot = 0;//在坐标轴上的点
        if (n < 4)
            maxShoot = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int X1 = x[j] - x[i];
                int Y1 = y[j] - y[i];
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j)
                        continue;
                    int count = 3;
                    for (int l = 0; l < n; l++) {
                        if (l == i || l == j || l == k)
                            continue;
                        int X2 = x[l] - x[k];
                        int Y2 = y[l] - y[k];
                        int X3 = x[l] - x[i];
                        int Y3 = y[l] - y[i];
                        if (X1 * X2 + Y1 * Y2 == 0 || X1 * Y3 == X3 * Y1)
                            count++;
                    }
                    if (count > maxShoot)
                        maxShoot = count;
                }
            }
        }
        System.out.println(maxShoot);
    }
}

发表于 2017-09-19 18:54:29 回复(0)

linanwx

分析

题目等价于，找一个十字架能够尽可能多的覆盖所有节点。
考虑到一根线至少能够覆盖到两个点，再加一根垂直于这条线至少能够覆盖3个点，在此基础上进行遍历。对任意三个点，我们选择其中两个点做一条直线(三种情况)，对于第三个点，我们做一条垂线到这条直线上。这样的十字架已经经过了三个点。对于剩下的点，我们判断是否在这个十字架上。要判断是否在十字架上，首先判断是否和第一条直线在同一条直线上。否则，判断这个点和第三个点所构成的直线是否和第二条直线垂直。
当点数小于等于3个点，则可以把所有点都覆盖到。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct point{
    int x = 0;
    int y = 0;
};

bool is_sameline(point p1, point p2, point p3){
    return ((p1.x - p2.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p2.y)) == 0;
}

bool is_vertical(point p1, point p2){
    return (p1.x * p2.x + p1.y * p2.y) == 0;
}

bool is_vertical(point p1, point p2, point p3, point p4){
    point v1, v2;
    v1.x = p1.x - p2.x;
    v1.y = p1.y - p2.y;
    v2.x = p3.x - p4.x;
    v2.y = p3.y - p4.y;
    return is_vertical(v1, v2);
}

int main()
{
    int n, ret = 0;
    cin >> n;
    point inputs[n];
    for (int i = 0; i < n; i++)
        cin >> inputs[i].x;
    for (int i = 0; i < n; i++)
        cin >> inputs[i].y;
    if (n < 4)
    {
        cout << n << endl;
        return 0;
    };
    vector<int> select = {1, 1, 1};
    for (int i = 0; i < n - 3; i++)
        select.push_back(0);
    do
    {
        vector<point> shizi;
        for (int i = 0; i < n; i++)
        {
            if (select[i])
            {
                shizi.push_back(inputs[i]);
            }
        }
        vector<vector<point>> status;
        status.push_back({shizi[0], shizi[1], shizi[2]});
        status.push_back({shizi[0], shizi[2], shizi[1]});
        status.push_back({shizi[1], shizi[2], shizi[0]});
        for (auto points : status)
        {
            int count = 0;
            for (int i = 0; i < n; i++)
            {
                if (!select[i])
                {
                    if (is_sameline(points[0], points[1], inputs[i]))
                        count++;
                    if (is_vertical(points[0], points[1], points[2], inputs[i]))
                        count++;
                }
            }
            ret = max(ret, count);

        }
    } while (prev_permutation(select.begin(), select.end()));
    cout << ret + 3 << endl;
    return 0;
}

发表于 2018-01-22 21:50:14 回复(0)

霍七

思路参考@littlebee
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

#include <iostream>
using namespace std;
int main()
{
    int n; cin >> n;
    int *x = new int[n];
    int *y = new int[n];
    int *dx = new int[n*n];
    int *dy = new int[n*n];
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> y[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dx[i*n + j] = x[i] - x[j];
            dy[i*n + j] = y[i] - y[j];
        }
    }
    int max = -1, temp;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int p = 0; p < n; p++) {
                if (p == i || p == j || dy[i*n + j] * dx[i*n + p] == dy[i*n + p] * dx[i*n + j]) continue;
                temp = 0;
                for (int q = 0; q < n; q++) {
                    if (dy[i*n + j] * dx[i*n + q] == dy[i*n + q] * dx[i*n + j] || dy[i*n + j] * dy[p*n + q] == -dx[i*n + j] * dx[p*n + q]) {
                        temp++;
                    }
                }
                max = max>temp ? max : temp;
            }
        }
    }
    max = max == -1 ? n : max;
    cout << max;
    delete[] x;
    delete[] y;
    delete[] dx;
    delete[] dy;
    return 0;
}

发表于 2017-10-10 10:43:49 回复(5)

元气の悟空

#include<stdio.h>
#define max(a,b) a>b?a:b
const int maxn=55;
int dx[maxn][maxn],dy[maxn][maxn],x[maxn],y[maxn];
int main(){
    int n,i,j,k,q,res,Max=-1;
    for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",&x[i]);
    for(i=0;i<n;i++) scanf("%d",&y[i]);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++) dx[i][j]=x[j]-x[i],dy[i][j]=y[j]-y[i];
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            for(k=0;k<n;k++)
                if(k!=i&&k!=j&&dy[i][j]*dx[i][k]!=dy[i][k]*dx[i][j]){
                    for(q=0,res=0;q<n;q++)
                        if(dy[i][j]*dx[i][q]==dy[i][q]*dx[i][j]
                            ||dy[i][j]*dy[k][q]==-dx[i][j]*dx[k][q])
                            res++;
                    Max=max(Max,res);
                }
    printf("%d\n",Max+1?Max:n);
}

发表于 2017-10-30 15:11:00 回复(2)

Yumho

clean and concise python solution

n = int(input())
x = list(map(int,input().strip().split()))
y = list(map(int,input().strip().split()))
res = min(n,3)
for i in range(n):
    for j in range(i+1,n):
        dy1 = y[j] - y[i]
        dx1 = x[j] - x[i]
        for k in range(j+1,n):
            cnt = 3
            for l in range(n):
                if l == i or l == j or l == k:
                    continue
                dy2 = y[k] - y[l]
                dx2 = x[k] - x[l]
                dy3 = y[i] - y[l]
                dx3 = x[i] - x[l]
                if dx1*dx2 + dy1*dy2 == 0 or dx1*dy3 == dx3*dy1:
                    cnt += 1
            res = max(res,cnt)
print(res)

发表于 2019-08-02 16:21:42 回复(2)

君之羽翼

我的方法，不是很好，但是至少是一个不同的思路。消耗空间，减少时间。

思路是：遍历选择两个点，计算出斜率，存入set集合，利用set的唯一性去除多余计算。令该斜率的直线以及垂直与它的直线都过原点，根据横坐标计算出纵坐标的差值，差值相同说明可以通过平移直线使其在直线上。接下来只要提取出差值的数量最多的差值及其数量。两条线的差值最多的数量相加，若存在平移后会落于原点的点，值减1。

需要注意斜率无穷大的处理（我处理为0），还有可能存在多种差值数量一样，那么需要综合这多个差值，只要某种差值下，不存在平移后会落于原点的点，可以不用继续考虑剩余的了。


	#include <stdio.h>



	#include <set>



	#include <map>



	using namespace std;



	





	int n;



	int x[50];



	int y[50];



	





	set<double> factors;



	





	int targetNum(int factor){



	    double offsetP[50];



	    double offsetN[50];



	    map<double,int> tmpOffsetPs;



	    map<double,int> tmpOffsetNs;



	





	    if (factor==0) {



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



	            offsetP[i]=y[i];



	            tmpOffsetPs[offsetP[i]]++;



	            offsetN[i]=x[i];



	            tmpOffsetNs[offsetN[i]]++;



	        }



	    }



	    else{



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



	            offsetP[i]=y[i]-factor*x[i];



	            tmpOffsetPs[offsetP[i]]++;



	            offsetN[i]=y[i]+1/factor*x[i];



	            tmpOffsetNs[offsetN[i]]++;



	        }



	    }



	





	





	    int offsetPNum=0;



	    double offsetPVal[50];



	    int offsetPValNum=0;



	    int offsetNNum=0;



	    double offsetNVal[50];



	    int offsetNValNum=0;



	    map<double,int>::iterator it;



	    for (it=tmpOffsetPs.begin(); it!=tmpOffsetPs.end(); it++) {



	        if (offsetPNum<(it->second)) {



	            offsetPNum=(it->second);



	            offsetPValNum=1;



	            offsetPVal[0]=(it->first);



	        }



	        else if (offsetPNum==(it->second)){



	            offsetPVal[offsetPValNum]=(it->second);



	            offsetPValNum++;



	        }



	    }



	    for (it=tmpOffsetNs.begin(); it!=tmpOffsetNs.end(); it++) {



	        if (offsetNNum<(it->second)) {



	            offsetNNum=(it->second);



	            offsetNValNum=1;



	            offsetNVal[0]=(it->first);



	        }



	        else if (offsetNNum==(it->second)){



	            offsetNVal[offsetNValNum]=(it->second);



	            offsetNValNum++;



	        }



	    }



	





	    int returnVal=offsetPNum+offsetNNum;



	    for (int j=0; j<offsetPValNum; j++) {



	        for (int k=0; k<offsetNValNum; k++) {



	            int tmpMask=0;



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



	                if (offsetP[i]==offsetPVal[j] && offsetN[i]==offsetNVal[k]) {



	                    tmpMask=1;



	                    break;



	                }



	            }



	            if (tmpMask==0) {



	                return returnVal;



	            }



	        }



	        



	    }



	    return returnVal-1;



	}



	





	





	void work(){



	    if (n==1) {



	        printf("%d",1);



	        return;



	    }



	    for(int i=0;i<n-1;i++){



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



	            if (x[i]==***>


	                factors.insert(0);



	            }



	            else



	                factors.insert(double(y[i]-y[j])/(x[i]-***>


	        }



	    }



	    int result=0;



	    set<double>::iterator it;



	    for (it=factors.begin(); it!=factors.end(); it++) {



	        int tmp = targetNum(*it);



	        result = result>=tmp ? result : tmp;



	    }



	    printf("%d",result);



	}



	





	int main(){



	    scanf("%d",&n);



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



	        scanf("%d",&x[i]);



	    }



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



	        scanf("%d",&y[i]);



	    }



	





	    work();



	}

发表于 2018-04-04 15:17:45 回复(0)

c++好难

思路就是找互相垂直的两条直线所能包含的最多的点

发表于 2018-08-22 08:33:47 回复(0)

ArthurV

本题的情况思路比较清晰，主要借助直线垂直与平行的情况来确定点数，
借助多重循环扫描寻找垂直和平行
主要依据是：两条垂直线可以通过以下变换转移至坐标轴位置，从而怪物被消灭
a)将垂直线整体平移，至垂直线交点为坐标轴原点
b)将两直线整体绕原点旋转一定度数，至两线分别与x,y轴重合

使用循环扫描时两种情况需要注意：1）当怪物少于4时，点数=怪物数量；
2）当所以怪物均共线时，点数=n
下附代码
#include <iostream>
using namespace std;
const int N = 51;

int XM[N];
int YM[N];
int main()
{     int n;     cin >> n;     for (int i = 0; i < n; i++)     {         cin >> XM[i];     }     for (int i = 0; i < n; i++)     {         cin >> YM[i];     }     int flag = 0;     int max = 0;     int t = 0;     for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             for (int k = 0; k < n; k++)             {                 if (i!=j&&i!=k&&j!=k)                 {                     if ((XM[i] - XM[j])*(YM[i] - YM[k]) != (XM[i] - XM[k])*(YM[i] - YM[j]))                         //不共线                     {                         flag = 1;                         t += 3;                         for (int m = 0; m < n; m++)                         {                             //点不重复                             if (i != m&&j != m&&k != m)                             {                                 if ((XM[i] - XM[j])*(YM[i] - YM[m]) == (XM[i] - XM[m])*(YM[i] - YM[j]))                                     //共线                                     t++;                                 else if ((XM[i] - XM[j])*(XM[k] - XM[m]) == (YM[i] - YM[j])*(YM[m] - YM[k]))                                     t++;                             }                         }                         if (t > max)                             max = t;                         t = 0;                     }                                                        }             }      if (n < 4)         max = n;     if (!flag)         max = n;     cout << max;     return 0;
}

发表于 2018-03-21 19:33:25 回复(2)

C/C++

Rain-y

我也来，思路就是暴力搜索哈

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> xs(n,0), ys(n,0);
    for(int i=0; i<n; i++) cin >> xs[i];
    for(int i=0; i<n; i++) cin >> ys[i];

    int ret = min(3, n);
    // 过point[i] 作关于 point[k] --- point[l] 的垂线
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(j==i) continue;  // 避免重复
            for(int k=j+1; k<n; k++){ // 交换 j,k 直线不变
                int dx = xs[j]-xs[k], dy = ys[j]-ys[k]; // j--k 方向向量
                int tmp = 0;
                for(int l=0; l<n; l++){
                    int ax1 = xs[l]-xs[i], ay1 = ys[l]-ys[i];   // l--i 方向向量
                    int ax2 = xs[l]-xs[j], ay2 = ys[l]-ys[j];   // l--j 方向向量
                    if(ax1*dx+ay1*dy==0 || ax2*dy-ay2*dx==0) tmp++; // 共线关系转换为垂直关系
                }
                ret = max(ret, tmp);
            }
        }
    }
    cout << ret << endl;
}

编辑于 2020-06-21 18:00:04 回复(0)

💤称奇

#同样四层for循环，python超时了，太不友好了
n = int(input().strip('\n'))
x = [int(i) for i in input().strip('\n').split(' ')]
y = [int(i) for i in input().strip('\n').split(' ')]
max_count = 0
for i in range(n):
    for j in range(n):
        if j == i:
            continue
        x1 = x[j] - x[i]
        y1 = y[j] - y[i]
        for k in range(n):
            if k == i or k == j:
                continue
            count = 3
            for t in range(n):
                if t == i or t == j or t == k:
                    continue
                x2 = x[t] - x[k]
                y2 = y[t] - y[k]
                if x1 * x2 + y1 * y2 == 0 or (x[t] - x[i]) * y1 == (y[t] - y[i]) * x1:
                    count += 1
            max_count = max(max_count, count)
if n <= 3:
    max_count = n
print(max_count)

发表于 2019-09-15 16:53:26 回复(2)

huluact

根据 littlebee的解析，使用python编写通过

n=int(input())
x_list=[int(x) for x in input().split(' ')]
y_list=[int(x) for x in input().split(' ')]
def run(x_list,y_list,n):
    max_num=0
    if n <= 3:
        return n
    else:
        flag_ABC_exits = 0 #是否存在ABC三点不共线的情况
        for i in range(n):
            for j in range(i + 1, n):
                dxAB = x_list[i] - x_list[j]  # AB
                dyAB = y_list[i] - y_list[j]
                for k in range(j + 1, n):
                    dxAC = x_list[i] - x_list[k]
                    dyAC = y_list[i] - y_list[k]
                    if dxAC * dyAB == dyAC * dxAB:  # ABC不共线
                        continue
                    num = 0
                    flag_ABC_exits = 1
                    for m in range(n):
                        if m == i or m == j or m == k:
                            continue
                        dxAD = x_list[i] - x_list[m]  # AD
                        dyAD = y_list[i] - y_list[m]
                        dxCD = x_list[k] - x_list[m]  # CD
                        dyCD = y_list[k] - y_list[m]
                        if dxAD * dyAB == dxAB * dyAD or dxCD * dxAB + dyCD * dyAB == 0: #D点在AB上或CD垂直AB
                            num += 1
                    num += 3
                    if num > max_num:
                        max_num = num
                if not flag_ABC_exits:
                    num = 0
                    for m in range(n):
                        if m == i or m == j:
                            continue
                        dxAD = x_list[i] - x_list[m]  # AD
                        dyAD = y_list[i] - y_list[m]
                        if dxAD * dyAB == dxAB * dyAD:
                            num += 1
                    num += 2
                    if num > max_num:
                        max_num = num
                if max_num == n:#如果max_num等于n,没有必要再循环了，跳出
                    return n
        return max_num
print(run(x_list,y_list,n))

发表于 2019-03-16 23:26:59 回复(1)

spMoon

这题用python实现4个循环的思路的话会超时，在这提醒用python的各位：）

发表于 2018-08-09 20:46:29 回复(0)

流浪打工人

路过，路过

#include<iostream>

#include<vector>
int main(void)
{
    using namespace std;
    int n;
    while (cin >> n)
    {
        vector<int> x(n);//存储横坐标
        vector<int> y(n);//储存纵坐标
        for (int i = 0; i < n; i++)
            cin >> x[i];
        for (int i = 0; i < n; i++)
            cin >> y[i];
        int max = 0;
        int flag1 = 0;
        int flag2 = 0;

        for (int i = 1; i < n; i++)
        {
            if (x[0] != x[i])
            {
                flag1 = 1;
                break;
            }
        }
        for (int i = 1; i < n; i++)
        {
            if (y[0] != y[i])
            {
                flag2 = 1;
                break;
            }
        }

        if (n < 4)
            cout << n << endl;
        else
        {

            for (int i = 0; i < n; i++)//选取第一个点
                for (int j = i + 1; j < n; j++)//选取第二个点
                {
                    int max_temp1 = 3;

                    for (int k = j + 1; k < n; k++)//选取第三个点
                    {

                        if ((x[j] - x[i])*(y[k] - y[i]) != (y[j] - y[i])*(x[k] - x[i]))//如果前面三个点共线，跳过第四个点的选取
                        {

                            for (int l = 0; l < n; l++)//选取第四个点
                            {
                                if (l != i && l != j && l != k)
                                {
                                    if ((x[l] - x[i])*(y[j] - y[i]) == (y[l] - y[i])*(x[j] - x[i]))
                                    {
                                        max_temp1++;
                                    }
                                    else
                                        if ((x[j] - x[i])*(x[l] - x[k]) + (y[j] - y[i])*(y[l] - y[k]) == 0)
                                        {
                                            max_temp1++;
                                        }
                                }
                            }
                        }
                        if (flag1 == 0 || flag2 == 0)//判断是否全部点共线
                            max_temp1 = n;
                        if (max_temp1 > max)
                            max = max_temp1;
                        max_temp1 = 3;
                    }

                }
            cout << max << endl;
        }
    }
    system("pause");
}

发表于 2018-05-19 20:19:56 回复(0)

逗比请来的猴子

/*
 * 参考大神的解题思路：https://www.nowcoder.com/questionTerminal/d3f26db0325444078717cc802e0056d8
 *
 * 使用四次循环，分别用于挑选不同的四个点；
 * 第一次和第二次循环挑选好为x轴的直线，第三次和第四次用于挑选好y轴；
 * 然后在整个遍历的过程中选择最大的值
 * */
public class MaxShot {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] x = new int[n];
            int[] y = new int[n];
//            录入所有点的坐标值
            for (int i = 0; i < n; i++) {
                x[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                y[i] = scanner.nextInt();
            }

            int maxShot = 0;
            if (n < 4) {
                maxShot = n;
            } else {
//                            确定x轴
                for (int i = 0; i < n - 1; i++) {
                    for (int j = i + 1; j < n; j++) {
                        int x1 = x[j] - x[i];
                        int y1 = y[j] - y[i];
                        for (int k = 0; k < n; k++) {
//                            确定y轴的一个点
                            if (k == i || k == j) {
                                continue;
                            }
                            int tmp = 3;
//                            变换另一个点
                            for (int l = 0; l < n; l++) {
                                if (l == i || l == j || l == k) {
                                    continue;
                                }
                                int x2 = x[l] - x[i];
                                int y2 = y[l] - y[i];
                                int x3 = x[l] - x[k];
                                int y3 = y[l] - y[k];
//                                该点在x轴或者y轴上添加进来
                                if (x1 * y2 == x2 * y1 || x1 * x3 + y1 * y3 == 0) {
                                    tmp++;
                                }
                                maxShot = Math.max(maxShot, tmp);
                            }
                        }
                    }
                }
            }
            System.out.println(maxShot);
        }
    }
}

发表于 2018-03-27 11:08:36 回复(0)

hugo_law

根据littlebee大佬的思路写出来的代码

import java.util.Scanner;
public class Main{
private int m=0;
private int[] mx;
private int[] my;
public Main(int ms,int[] mxs,int[] mys){
this.m=ms;
this.mx=mxs;
this.my=mys;
}
//判断三点是否一线
public boolean judgeSameLine(int i,int j,int k){
if((mx[i]-mx[j])*(my[j]-my[k])==(mx[j]-mx[k])*(my[i]-my[j]))
return true;
return false;
}
//判断线ij和kl是否垂直
public boolean judgeVertical(int i,int j,int k, int l){
if((my[i]-my[j])*(my[k]-my[l])+(mx[i]-mx[j])*(mx[k]-mx[l])==0)
return true;
return false;
}
public static void main(String[] args){
int n=0;//怪物数
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
int[] dx = new int[n];
int[] dy = new int[n];
for(int i=0;i<n;i++){
dx[i]=sc.nextInt();
}for(int i=0;i<n;i++){
dy[i]=sc.nextInt();
}
Main mai = new Main(n,dx,dy);
int max=0;//最大消灭数
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
for(int k=j+1;k<n;k++){
if(mai.judgeSameLine(i,j,k))continue;
int count=0;//记录当前建立的坐标轴可消除的数量
for(int l=0;l<n;l++){
if(mai.judgeSameLine(i,j,l)||mai.judgeVertical(i,j,k,l))
count++;
if(count>max)max=count;
}
}
}
}
//当n<3或全部点在一条直线上时，上面4个for循环不生效，且此时可以全部消灭，故max=n
if(max==0)max=n;
System.out.print(max);
sc.close();
}
}

发表于 2018-03-02 17:31:58 回复(0)

梦境迷离

原来考数学的我去

发表于 2018-02-16 16:29:11 回复(0)

Java

symfony

/**
* 解题思路：点不变，坐标系旋转，看最多能有多少点在坐标系上；
*
* @author symfony
*
*/
public class Demo7 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] x = new int[num];
        int[] y = new int[num];
        for (int i = 0; i < num; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 0; i < num; i++) {
            y[i] = sc.nextInt();
        }
        if (num <= 3) {
            // 三点构成一个坐标系，直接返回
            System.out.println(num);
            return;
        }
        int max = 0;
        for (int i = 0; i < num; i++) {
            for (int j = i + 1; j < num; j++) {
                // 此时取两点 i,j; 坐标为(x[i],y[i]),(x[j],y[j])
                // rp 记录直线i,j上的点的个数; 开始就有i,j两点,所以rp=2;
                int rp = 2;
                for (int s = 0; s < num; s++) {
                    if (s != i && s != j) {
                        if ((x[s] - x[i]) * (y[s] - y[j]) == (x[s] - x[j]) * (y[s] - y[i])) {
                            // s点和i，j在同一条直线上
                            rp++;
                        }
                    }
                }
                if (rp == num || rp == (num - 1)) {
                    // 当所以点都在一条直线上,或者只有一点不在直线上,则直接返回num;
                    System.out.println(num);
                    return;
                }
                // System.out.println(i + "到" + j + "有：" + rp);
                int tmp = rp;
                // 找出直线外一点,以及过这一点与i,j垂直的直线上点的个数;
                for (int m = j + 1; m < num; m++) {
                    if ((x[m] - x[i]) * (y[m] - y[j]) == (x[m] - x[j]) * (y[m] - y[i])) {
                        // m点和i，j在同一条直线上
                        continue;
                    } else {
                        for (int n = 0; n < num; n++) {
                            if (n == m || n == i || n == j) {
                                continue;
                            }
                            if ((x[n] - x[i]) * (y[n] - y[j]) == (x[n] - x[j]) * (y[n] - y[i])) {
                                // n点和i，j在同一条直线上
                                continue;
                            }
                            if ((y[j] - y[i]) * (y[m] - y[n]) + ((x[j] - x[i]) * (x[m] - x[n])) == 0) {
                                tmp++;
                            }
                        }
                        tmp++;// 加上m点;
                        // 此时判断i与j连线外一点m，有多少点与m相连的直线与ij垂直
                        // System.out.println(i+"==>"+j+"==>"+m+"系统有:"+tmp);
                        if (tmp > max) {
                            max = tmp;
                            System.out.print(tmp + "==");
                        }
                        tmp = rp;
                    }
                }
            }
        }
        System.out.println("res:" + max);
    }
}

发表于 2017-12-18 12:58:07 回复(0)

Anascetic


import java.util.Scanner;

public class Test1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n], b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }

        if (n < 3) {
            System.out.println(n);
            return;
        }

        int max = 3;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double k1 = (b[i] - b[j]) / (a[i] - a[j] + 0.0);
                double b1 = b[i] - k1 * a[i];
                for (int k = j + 1; k < n; k++) {
                    int count = 0;
                    for (int l = k + 1; l < n; l++) {
                        if (k1 * a[l] + b1 == b[l]) {
                            count++;
                            continue;
                        }
                        double k2 = (b[l] - b[k]) / (a[l] - a[k] + 0.0);
                        if (k2 * k1 == -1)
                            count++;
                    }
                    max = Math.max(max, count);
                }
            }
        }

        System.out.println(max);
    }
}

发表于 2017-11-15 21:17:36 回复(0)

牛客1298507号

两重循环计算任意两点所连直线的倾斜角，全部映射到0-90度区间，使得平行和垂直的直线倾斜角相等最后统计各倾斜角的频率，频率最高的就是所求 import java.util.*; public class Main { public static void main(String[] args{ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int x[] = new int[n]; int y[] = new int[n]; double dd[] = new int[n*(n+1)/2]; for (int i = 0; i < n; i++) x[i] = scan.nextInt(); for (int i = 0; i < n; i++) y[i] = scan.nextInt(); scan.close(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { dd[i*n+j] = Math.atan((x[j] - x[i]) / (y[j] - y[i])); if (dd[i*n+j]<0) dd[i*n+j] += Math.toRadians(90); } } Map<String,Integer> map = new HashMap<>(); for (double k : dd) { string str = String.format("%.6f", k); if (map.containsKey(str)){ map.put(str,map.get(str)+1); }else { map.put(str,1); } } Collection<Integer> c = map.values(); Object[] obj = c.toArray(); Arrays.sort(obj); System.out.println(obj[obj.size()-1]); } }

发表于 2017-10-17 01:20:49 回复(0)