计算几何
#include <stdio.h> #include <stdlib.h>
const int LEN = 205;
typedef struct { int x; int y; int addr; }point; point p[LEN];
typedef struct { point b; point e; }type; type line[LEN*LEN*2];
void cpy ( point *a, const point *b ) {
a->x = b->x; a->y = 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 )->x - ( ( point * )b )->x; if ( ! ans ) { ans = ( ( point * )a )->y - ( ( point * )b )->y; }
return ans; }
int cmp2 ( const void *a, const void *b ) {
type *c = ( type * )a; type *d = ( 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[LEN];
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;
scanf ( "%d", &n );
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 ( int 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 ( int 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; }
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
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)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|