问题标题: 酷町堂：4760 飞行员酷町猫

Question

0

已解决

汪宇航

新手启示者

大佬们，95分！！！还是黄色的！！！

怎么做啊😭😭😭😭😭???

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

输入描述 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

汪宇航在2021-02-09 12:33:53追加了内容

第一个帮我做对的可以领悬赏！！！

拜托啦。。。。。。。。。。。。。。。

Answer 1

已采纳

汪恺恒

中级启示者

核心（暴力枚举）

for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++){  //遍历坐标
                定义 c=b[j]-b[i],d=a[i]-a[j],e=b[i]*a[j]-b[j]*a[i],cnt=0;
                for(int k=1;k<=n;k++){
                    如果(c*a[k]+d*b[k]+e==0) cnt++;  //如果是直线
                }
                ans=max(ans,cnt);
           }
    }

注意特判：如果n==1 输出1

Answer 2

汪宇航

新手启示者

大佬求解。。。

问题标题: 酷町堂：4760 飞行员酷町猫

2 个回答: