[POJ1118]Lining Up

 

Time Limit: 2000MS		Memory Limit: 32768K
Total Submissions: 24071		Accepted: 7564

Description

"How am I ever going to solve this problem?" said the pilot. 

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number? 


Your program has to be efficient! 

Input

Input consist several case,First line of the each case is an integer N ( 1 < N < 700 ),then follow N pairs of integers. Each pair of integers is separated by one blank and ended by a new-line character. The input ended by N=0.

Output

output one integer for each input case ,representing the largest number of points that all lie on one line.

Sample Input

5
1 1
2 2
3 3
9 10
10 11
0

Sample Output

3

Source

East Central North America 1994

THINKING

　　搜索，分别判断X轴，Y轴，斜率即可。

type point=record
    x,y:longint;
    end;

var a:array[0..5000] of point;
    f:array[0..5000] of longint;
    i,j,ans,sum,pred,n,xx,yy,g,k,aa,bb,x:longint;

function max(x,y:longint):longint;
begin
    if x>y then exit(x) else exit(y);
end;

procedure sort(l,r: longint);
      var
         i,j,x: longint;y:point;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].x;
         repeat
           while a[i].x<x do
            inc(i);
           while x<a[j].x do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure sort1(l,r: longint);
      var
         i,j,x: longint;y:point;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].y;
         repeat
           while a[i].y<x do
            inc(i);
           while x<a[j].y do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort1(l,j);
         if i<r then
           sort1(i,r);
      end;

procedure main;
begin
    if n<=2 then
        begin
            writeln(n);
            halt;
        end;
    if n=3 then
        if(abs(a[2].x-a[1].x)=abs(a[3].x-a[2].x))and(abs(a[2].y-a[1].y)=abs(a[3].y-a[2].y)) then
            begin
                writeln(3);
                halt;
            end
        else
            begin
                writeln(2);
                halt;
            end;
    //特殊判断
    sort(1,n);
    ans:=0;
    sum:=1;
    pred:=a[1].x;
    for i:=2 to n do
        if a[i].x=pred then inc(sum)
        else
            begin
                ans:=max(ans,sum);
                pred:=a[i].x;
                sum:=1;
            end;
    //判断横
    ans:=max(ans,sum);
    sort1(1,n);
    sum:=1;
    pred:=a[1].y;
    for i:=2 to n do
        if a[i].y=pred then inc(sum)
        else
            begin
                ans:=max(ans,sum);
                pred:=a[i].y;
                sum:=1;
            end;
    //判断纵
    ans:=max(ans,sum);
    for i:=1 to n do
        for j:=i+1 to n do
            begin
                sum:=2;
                for k:=j+1 to n do
                    begin
                        aa:=(a[i].y-a[k].y)*(a[j].x-a[k].x);
                        bb:=(a[i].x-a[k].x)*(a[j].y-a[k].y);
                        if aa=bb then inc(sum);
                    end;
               ans:=max(ans,sum);
            end;
    //判断斜率
    writeln(ans);
end;

begin
    while true do
        begin
            readln(n);
            if n=0 then halt;
            for i:=1 to n do
                readln(a[i].x,a[i].y);
            main;
        end;
end.