11350: 【原1350】穿越沙漠

题目

题目描述

author: SSY 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1350

Description

塞尔达公主又又又又被抓走了。林克为了找到她需要穿过拉纳鲁沙漠，坏消息是林克可能没有足够的体力穿越沙漠，好消息是沙漠中分布着N个力之果实，坏消息是我们的林克只能走直线。为了穿越沙漠，林克希望能够吃到尽可能多的力之果实。现在请你帮他规划一条直线，使他能够获得尽可能多的力之果实。

Input Format

输入第一行有一个数N，表示沙漠中果实的数量。

接下来的N行每行两个正整数x,y，表示每个力之果实的坐标。

Output Format

输出一个数，表示林克最多能够获得的力之果实的数量。

Sample Input

5
4 4
2 2
9 9
9 11
17 8

Sample Output

3

说明

对于70%的数据，N<=300

对于100%的数据，N<=700

yyong119's solution

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX_N 705
#define INF 0x3f3f3f3f
using namespace std;

int n;
int x[MAX_N], y[MAX_N];

int main() {

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
    int max = 2;
    for (int i = 0; i < n; ++i) {
        double tan[n];
        memset(tan, 0, sizeof(tan));
        tan[i] = INF + 1;
        for (int j = 0; j < n; ++j)
            if (i != j)
                if (x[i] == x[j])
                    tan[j] = INF;
                else
                    tan[j] = (double)(y[j] - y[i]) / (x[j] - x[i]);

        sort(tan, tan + n);
        int tmp_max = 0, cnt = 1;
        for (int j = 1; j < n; ++j)
            if (tan[j] == tan[j - 1])
                ++cnt;
            else {
                if (cnt > tmp_max)
                    tmp_max = cnt;
                cnt = 1;
            }
        if (tmp_max + 1 > max) max = tmp_max + 1;
    }
    cout << max << endl;
    return 0;
}