计算几何
#include <stdio.h> #include <stdlib.h>
const int LEN = 1010;
struct { int flag; int up; int down; }hash[LEN][LEN]; int flag;
struct { int x; int y; }point[LEN];
void inith ( int n ) {
flag = 1; for ( int i=0; i<n; i++ ) { for ( int j=0; j<n; j++ ) { hash[i][j].flag = 0; } } }
int cmp ( const void *a, const void *b ) {
int ans = *( ( int * )a ) - *( ( int * )b ); if ( ! ans ) { ans = *( ( int * )a + 1 ) - *( ( int * )b + 1 ); } return ans; }
int gdc ( int a, int b ) { if ( a == 0 ) { return b; } if ( b == 0 ) { return a; } return gdc ( b, a%b ); }
int find ( int n ) {
qsort ( point, n, sizeof ( point[0] ), cmp );
inith ( LEN-1 ); int max = -1; int temp; for ( int i=0; i<n; i++ ) { temp = -1; for ( int j=i+1; j<n; j++ ) { int a = point[j].x - point[i].x; int b = point[j].y - point[i].y; int pub; if ( a == 0 ) { b = 1; } else { pub = gdc ( a, b ); if ( pub < 0 ) { pub = -pub; } a /= pub; b /= pub; } if ( b < 0 ) { if ( hash[a][-b].flag != flag ) { hash[a][-b].up = 0; hash[a][-b].down = 0; hash[a][-b].flag = flag; } hash[a][-b].down ++;
if ( temp < hash[a][-b].up ) { temp = hash[a][-b].up; } if ( temp < hash[a][-b].down ) { temp = hash[a][-b].down; } } else { if ( hash[a][b].flag != flag ) { hash[a][b].up = 0; hash[a][b].down = 0; hash[a][b].flag = flag; } hash[a][b].up ++;
if ( temp < hash[a][b].up ) { temp = hash[a][b].up; } if ( temp < hash[a][b].down ) { temp = hash[a][b].down; } } } if ( max < temp + 1 ) { max = temp + 1; } flag ++; }
return max; }
int main () {
int n;
while ( scanf ( "%d", &n ) != EOF ) { for ( int i=0; i<n; i++ ) { scanf ( "%d%d", &point[i].x, &point[i].y ); }
printf ( "%d\n", find ( n ) ); } return 0; }
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|