一个计算机和的题目,要做的事最多有多少个点共线,做法是对线段进行排序,然后查找。注意HASH。
#include < stdio.h >

#include 
< stdlib.h >

typedef struct
{
    
int x;
    
int y;
    
int addr;
}
point;
point p[
701];

typedef struct
{
    point b;
    point e;
}
type;
type line[
250000];

void cpy ( point *a, const point *b )
{
    
    a
->= b->x;
    a
->= b->y;
    a
->addr = b->addr;
}


int mul ( type *l1, type *l2 )
{
    
    
int x1 = l1->e.x - l1->b.x;
    
int y1 = l1->e.y - l1->b.y;
    
int x2 = l2->e.x - l2->b.x;
    
int y2 = l2->e.y - l2->b.y;
    
    
return x1 * y2 - x2 * y1;
}


int cmp1 ( const void *a, const void *b )
{
    
    
int ans = ( ( point * )a )->- ( ( point * )b )->x;
    
if ( ! ans )
    
{
        ans 
= ( ( point * )a )->- ( ( point * )b )->y;
    }

    
    
return ans;
}


int cmp2 ( const void *a, const void *b )
{
    
    type 
*= ( type * )a;
    type 
*= ( type * )b;
    type f;
    
int ans = - mul ( c, d );

    
if (  !ans )
    
{
        cpy ( 
&f.b, &( c->e ) );
        cpy ( 
&f.e, &( d->b ) );
        ans 
= - mul ( c, &f );
    }


    
return ans;
    
}


int hash[701];

void init ( int n )
{
    
    
for ( int i=0; i<n; i++ )
    
{
        hash[i] 
= 0;
    }

}


int main ()
{
    
    
int n;
    
int addr;
    
int max;
    
int count;
    
int number;
    
    
while ( 1 )
    
{
        scanf ( 
"%d"&n );
        
if ( n == 0 )
        
{
            
break;
        }


        
for ( int i=0; i<n; i++ )
        
{
            scanf ( 
"%d%d"&p[i].x, &p[i].y );
            p[i].addr 
= i;
        }

        
        qsort ( p, n, sizeof ( point ), cmp1 );
        addr 
= 0;
        
for ( i=0; i<n-1; i++ )
        
{
            
for ( int j=i+1; j<n; j++ )
            
{
                cpy ( 
&line[addr].b, &p[i] );
                cpy ( 
&line[addr].e, &p[j] );
                addr 
++;
            }

        }

        qsort ( line, addr, sizeof ( type ), cmp2 );            
        
        number 
= 1;
        max 
= -1;
        init (n);
        count 
= 2;
        hash[ line[
0].b.addr ] = number;
        hash[ line[
0].e.addr ] = number;
        
if ( count > max )
        
{
            max 
= count;
        }


        
for ( i=1; i<addr; i++ )
        
{
            
if ( ! cmp2 ( &line[i], &line[i-1] ) )
            
{
                
if ( hash[ line[i].b.addr ] != number )
                
{
                    count 
++;
                    hash[ line[i].b.addr ] 
= number;
                }

                
if ( hash[ line[i].e.addr ] != number )
                
{
                    count 
++;
                    hash[ line[i].e.addr ] 
= number;
                }

            }

            
else
            
{
                
if ( count > max )
                
{
                    max 
= count;
                }

                number 
++;
                count 
= 2;
                hash[ line[i].b.addr ] 
= number;
                hash[ line[i].e.addr ] 
= number;
            }

        }


        
if ( count > max )
        
{
            max 
= count;
        }

        
        printf ( 
"%d\n", max );
    }

    
return 0;
}