題目大意：
給出n個(gè)點(diǎn)，問你最多能連多少條線，保證這些線都不平行
思路：
計(jì)算每?jī)牲c(diǎn)斜率，用分?jǐn)?shù)的形式表示，然后哈希判重。要考慮斜率不存在和斜率為0的情況
#include <stdio.h>
int hash[2][2024][2064/32], hori, vert;
struct node 
{
int x, y;
} points[256];
int N, line_cnt;
__inline int gcd(int a, int b)
{
int r;
if (a < b) {
r = a;
a = b;
b = r;
}
while (1) {
r = a % b;
if (!r)
return b;
a = b;
b = r;
}
}
__inline int test_bit(int *arr, int idx)
{
return arr[idx >> 5] & (1 << (idx & 0x1f));
}
__inline int set_bit(int *arr, int idx)
{
return arr[idx >> 5] |= (1 << (idx & 0x1f));
}
__inline int abs(int i)
{
return i < 0 ? -i : i;
}
__inline void gril(struct node *pa, struct node *pb)
{
int dx, dy, neg, r;
dx = pa->x - pb->x;
dy = pa->y - pb->y;
if (!dx) {
if (vert)
return ;
vert = 1;
line_cnt++;
return ;
}
if (!dy) {
if (hori)
return ;
hori = 1;
line_cnt++;
return ;
}
neg = dx*dy < 0;
dx = abs(dx);
dy = abs(dy);
r = gcd(dx, dy);
dx /= r;
dy /= r;
if (test_bit(hash[neg][dx], dy))
return ;
set_bit(hash[neg][dx], dy);
line_cnt++;
}
int main()
{
int i, j;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
for (i = 0; i < N; i++)
scanf("%d%d", &points[i].x, &points[i].y);
for (i = 0; i < N - 1; i++) {
for (j = i + 1; j < N; j++) {
gril(&points[i], &points[j]);
}
}
printf("%d\n", line_cnt);
return 0;
}