学步园

/*************************************************************
题意：给你一些点，最多700个，问你最多有多少个点共线
思路：一每个点为中心，级角排序，再扫一遍
**************************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
struct Point
{
    int x, y;
    Point(int a = 0, int b = 0): x(a), y(b){}
    Point operator-(const Point &t) {return Point(x - t.x, y - t.y); }
}point[777], p[777];
char s[111];
int n;

int cross(const Point &a, const Point &b){return a.x * b.y - a.y * b.x; }
int dot(const Point &a, const Point &b){return a.x * a.y + b.y * b.x; }

bool cmp(const Point &a, const Point &b)
{
    if(a.y == 0 && a.x >= 0 && b.y != 0) return true;
    if(b.y == 0 && b.x >= 0 && a.y != 0) return false;
    if(a.y == 0 && b.y == 0)
    {
        if(a.x > 0 && b.x < 0) return true;
        if(a.x < 0 && b.x > 0) return false;
        return abs(a.x) < abs(b.x);
    }
    if(a.y > 0 && b.y < 0) return true;
    if(a.y < 0 && b.y > 0) return false;
    int c = cross(a, b);
    return c > 0;
}

int solve(int center)
{
    int i, j, ans=0;
    for(i=0, j=0; i < n; i++) if(i != center)
    {
        p[j++] = point[i] - point[center];
    }
    sort(p, p + n - 1, cmp);
    for(i = 1, j = 1; i < n - 1; i++)
    {
        if(cross(p[i], p[i-1]) == 0) j++;
        else j = 1;
        ans = max(ans, j);
    }
    return ans + 1;
}

int main()
{
    //freopen("uva270.in", "r", stdin);
    int T;
    scanf("%d", &T);
    gets(s);
    gets(s);
    while(T--)
    {
        int i, j, ans = 0;
        n = 0;
        while(gets(s) != NULL && strlen(s) > 0)
        {
            //puts(s);
            sscanf(s, "%d %d", &point[n].x,&point[n].y);
            n++;
        }
        for(i = 0; i < n; i++) ans = max(ans, solve(i));
        printf("%d\n", ans);
        if(T > 0) puts("");
    }
    return 0;
}