计算几何
#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)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|