九度 1548 平面上的点(技巧题)

题目描述：

给定平面上的n个点，任意做一条直线，求至多能有几个点恰好落在直线上。

 

思路

1. Leetcode 上原题. 解法是先确定一个点, 然后计算其他点相对于这个点的斜率

2. 这道题需要注意多点重合, 斜率为无穷大的情况

 

代码 未通过九度测试

#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;

int xs[200], ys[200];

int main() {
freopen("testcase.txt", "r", stdin);
int pointnum, x, y;
while(scanf("%d", &pointnum) != EOF) {
int retVal = 0, inf = 0, dup = 1;

for(int i = 0; i < pointnum; i ++) {
            scanf("%d%d", &x, &y);
            xs[i] = x, ys[i] = y;
        }

for(int i = 0; i < pointnum; i ++) {
            map<double, int> record;
int basex = xs[i], basey = ys[i];
for(int j = 0; j < pointnum; j ++) {
if(i == j) continue;
int newx = xs[j], newy = ys[j];
if(newx == basex && newy == basey) {
                    dup ++;
                }else if(newx == basex) {
                    inf++;
                }else{
                    record[((double)(newy-basey))/(newx-basex)] ++;
                }
            }
int party = 0;
            map<double, int>::iterator it_map;
for(it_map = record.begin(); it_map != record.end(); it_map ++) {
                party = max(party, it_map->second);
            }
            party = max(party, inf);
            party += dup;
            retVal = max(party, retVal);
        }


        printf("%d\n", retVal);
    }
return 0;
}