题解 | Game of Lines-牛客假日团队赛7K题

题目描述

Farmer John has challenged Bessie to the following game: FJ has a board with dots marked at $N (2 ≤ N ≤ 200)$ distinct lattice points. Dot i has the integer coordinates $X_i$ and $Y_i (-1,000 ≤ X_i ≤ 1,000; -1,000 ≤ Y_i ≤ 1,000)$ .
Bessie can score a point in the game by picking two of the dots and drawing a straight line between them; however, she is not allowed to draw a line if she has already drawn another line that is parallel to that line. Bessie would like to know her chances of winning, so she has asked you to help find the maximum score she can obtain.

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 describes lattice point i with two space-separated integers: $X_i$ and $Y_i.$

输出描述:

* Line 1: A single integer representing the maximal number of lines Bessie can draw, no two of which are parallel.

示例1

输入

4
-1 1
-2 0
0 0
1 1

输出

4

说明

Bessie can draw lines of the following four slopes: -1, 0, 1/3, and 1.

解答

这道题用一次函数去求斜率，然后用map存储是否有这样斜率的直线，判重
设一次函数解析式为 $y=k_x+b$ 现在告诉你横纵坐标去求 $k$
$y_1=k _{x1}+b , y_2=k_ {x2}+b$ 则 $k=(y_1-y_2)/(x_1-x_2)$
由于斜率不一定为整型数，所以 $double k=(y_1-y_2)\times1.0\div(x_1-x_2)$
But! 当 $x_1=x_2$ 时，除数为 $0$ 会出错，所以需要特判

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,a[201][2],s;
map<double,bool>xl;//开一个以double为下标的bool类型数组
double x;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i][0]>>a[i][1];//输入
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){//两两之间算斜率
            if(a[i][0]==a[j][0]) x=10000;//特判
            else x=(a[i][1]-a[j][1])*1.0/(a[i][0]-a[j][0]);
            if(!xl[x]) s++,xl[x]=1;//如果没有出现过，斜率累加，更新为出现过
        }
    cout<<s;//输出总数
    return 0;
}

来源:hmh13951417981