问题标题: 酷町堂：求4760 飞行员酷町猫 200豆子！

Question

0

被禁言

杜明泽

资深守护

4760 飞行员酷町猫

经验值：1200 时间限制：1000毫秒

题目描述 Description

飞行员酷町猫最近需要给一个地区的若干村庄空投补给，这些村庄是平面上的一些点。由于燃料问题，酷町猫只能飞一次。而且飞机很破，只能直行而不能拐弯。现在它想一次性给最多的村庄送补给。

输入描述 Input Description

第一行为n

接下来n行由n对整数组成(1≤n≤700)，每对整数表示一个点的坐标。没有一个点会出现两次。

输出描述 Output Description

一个整数，表示一条直线能覆盖的最多的点数。

样例输入 Sample Input

5 1 1 2 2 3 3 9 10 10 11

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

村庄的位置横纵坐标不超过100

酷町豆刷题求解 C++ 循环 0条评论 3 年，5 月前

Answer 1

马烨烨

初级守护

   cin>>n;
   for(int i=1;i<=n;i++)
   {
       (x[i],y[i])表示一个点的位置
   }
（点之间的两两搭配找出所有的线，判断其他点在这条线上）
枚举第一个点(x[i],y[i])
   {
       枚举第一个点(x[j],y[j]),两点确定一条线
           枚举其他点
              判断第k个点是否在枚举的线上
               (y[j]-y[i])*(x[k]-x[i])==(y[k]-y[i])*(x[j]-x[i])


       }
   }

马烨烨在2021-06-18 07:12:46追加了内容

注意！cnt在循环的初始值为2！！！！

马烨烨在2021-06-18 07:14:02追加了内容

在某层循环内要定义maxn，来比较cnt!!

Answer 2

朱欣然

高级守护

核心： cin>>n;
   for(int i=1;i<=n;i++){
       cin>>x[i]>>y[i];//(x[i],y[i])表示一个点的坐标
   }
//（点之间两两搭配找出所有的线，判断其他点在这条线上）

for(int i=1;i<=n;i++){//枚举第一个点（x[i],y[i]),两点确定一条直线
       for(int j=i+1;j<=n;j++){
           cnt=2;
           for(int k=j+1;k<=n;k++){//枚举其他点
//判断第k个点是否在枚举的线上
               if((y[j]-y[i])*(x[k]-x[i])==(y[k]-y[i])*(x[j]-x[i])){
                   cnt++;
               }
           }
           maxn=max(maxn,cnt);
       }
   }
   cout<<maxn;