POJ 3512 - Incidental Point

http://poj.org/problem?id=3512

概要

N 個の格子点の座標 (X, Y) が与えられる．

線分 P1P2 に含まれる点の数が最大になるように点 P1, P2 を選んだとき，含まれる点の数を答える．

制約

• N <= 1000
• 0 <= |X|, |Y| <= 1000000

解法

P1 を固定すれば，P1 を始点とする線分の傾きを求めて重複しているものを数えて最大値をとればいい．

傾きは適当に正規化しておく． 自分は x 方向の増分が非負になるように正規化した．

また，重複を数えるときに map, int> で数えると TLE した． Java の3倍ルール + HashMap か，配列を sort して 自力で重複を数えるようにすると通った．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 pair<int,int> parse(const char *buf)
 6 {
 7   int x, y;
 8   sscanf(buf, "%d %d", &x, &y);
 9   return make_pair(x, y);
10 }
11 
12 int gcd(int x, int y)
13 {
14   if (x <= y) {
15     swap(x, y);
16   }
17   if (y == 0) {
18     return x;
19   }
20   int r;
21   while ((r = x % y) != 0) {
22     x = y;
23     y = r;
24   }
25   return y;
26 }
27 
28 int main()
29 {
30   char buf[80];
31   int Ti = 0;
32   while (fgets(buf, sizeof buf, stdin) && !(buf[0] == '-' && buf[1] == '-')) {
33     static pair<int,int> ps[1000];
34     ps[0] = parse(buf);
35     int N = 1;
36     while (fgets(buf, sizeof buf, stdin) && !(buf[0] == '-' && buf[1] == '-')) {
37       ps[N++] = parse(buf);
38     }
39 
40     int ans = 0;
41     for (int i = 0; i < N; i++) {
42       static long long m[1000];
43       for (int j = i+1; j < N; j++) {
44         int dx = ps[j].first - ps[i].first;
45         int dy = ps[j].second - ps[i].second;
46         if (dx < 0) {
47           dx = -dx;
48           dy = -dy;
49         }
50         int g = gcd(dx, dy);
51         m[j] = (dx/g + 1000000L)*2000000LL + dy/g;
52       }
53       sort(m+i+1, m+N);
54       for (int j = i+1; j < N;) {
55         int k = j;
56         while (k < N && m[k] == m[j]) {
57           ++k;
58         }
59         ans = max(ans, k - j + 1);
60         j = k;
61       }
62     }
63     printf("%d. %d\n", ++Ti, ans);
64   }
65   return 0;
66 }