POJ 2606 - Rabbit hunt

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

概要

2次元平面上の整数値の座標に N 匹のウサギがいる．

一直線に並んでいるウサギは同時に撃つことができる．

最大で同時に何匹撃てるかを答える．

制約

• 2 <= N <= 200
• -100 <= x,y <= 1000

解法

O(N^3) で全通り試して数える．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int solve(const vector<pair<int,int> >& v, int i, int j)
 7 {
 8   const int N = v.size();
 9   const int dx = v[j].first - v[i].first;
10   const int dy = v[j].second - v[i].second;
11   int c = 0;
12   for (int k = 0; k < N; k++) {
13     if (k == i) {
14       continue;
15     }
16     const int dxx = v[k].first - v[i].first;
17     const int dyy = v[k].second - v[i].second;
18     if (dx * dyy == dy * dxx) {
19       ++c;
20     }
21   }
22   return c+1;
23 }
24 
25 int main()
26 {
27   int N;
28   cin >> N;
29   vector<pair<int,int> > v(N);
30   for (int i = 0; i < N; i++) {
31     cin >> v[i].first >> v[i].second;
32   }
33   sort(v.begin(), v.end());
34 
35   int ans = 0;
36   for (int i = 0; i < N; i++) {
37     for (int j = i+1; j < N; j++) {
38       ans = max(ans, solve(v, i, j));
39     }
40   }
41   cout << ans << endl;
42   return 0;
43 }