SRM 283 DIV2 600 PowerSupply

問題

　デカルト平面上にN個の点(x_i, y_i)がある。そこにx-軸、y-軸、2つの対角軸のいずれかに平行な線を一本引く。この線からの距離がD以下となるような点の個数を最大化したい。最適な線を引いた場合にえられるこの様な点の個数の最大値を求めよ。
　0 ≦ N ≦ 50
　-1000000 ≦ x_i ≦ 1000000
　-1000000 ≦ y_i ≦ 1000000

方針

　まず、x-軸に平行な線を引く場合を考える。点を2つ選んでその2つの距離が2*D以下なら、その2つの点および2つの点の間にある点すべてを距離D以内に含むような線が引ける。これは幾何の問題で良く使う”ギリギリ”を考える手法。
　y-軸も同様に可能。対角軸に平行な線を考えるのはちょっと面倒。点(x1, y1)を通りx+y=0に平行な直線（L1と定義する）と点(x2, y2)を通りx+y=0に平行な直線（L2の定義する）の距離を計算する場合は、L1とx+y=0の距離をまず測り、次にL2とx+y=0の距離を測って、その差分を取ればよいことが分かる。

　あとは、平方根が出てくるので丸め誤差に注意。double使いたくない場合は、長さの2乗を考えればOK。

ソースコード

　md[]とかcd[]とか使ってるけど、これはmain diagonalとcollateral diagonalの略。それぞれ行列の対角成分を呼ぶ呼び方らしい（今日別の問題解いてるときに知った）。main diagonalは右下がりのいわゆる主対角成分。collateral diagonalは右上がりの対角成分。

view plainprint?

1. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
2. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
3.   
4. class PowerSupply {  
5.     int maxLen(vector<int> x, long long len) {  
6.         int ret = 0;  
7.   
8.         sort(x.begin(), x.end());  
9.         REP(i, x.size()) {  
10.             FOR (j, i, x.size()) {  
11.                 long long diff = x[j] - x[i];  
12.                 diff *= diff;  
13.                 if (diff <= len)  
14.                     ret = max(ret, j-i+1);  
15.             }  
16.         }  
17.   
18.         return ret;  
19.     }  
20.   
21. public:  
22.     int maxProfit(vector<int> x, vector<int> y, int D) {  
23.         int ret = 0;  
24.         int N = x.size();  
25.   
26.         vector<int> md = x;  
27.         vector<int> cd = x;  
28.   
29.         REP(i, N) md[i] = x[i] + y[i];  
30.         REP(i, N) cd[i] = x[i] - y[i];  
31.   
32.         long long D1 = 4LL * D * D;           // orthogonal  
33.         long long D2 = 8LL * D * D;              // diagonal  
34.   
35.         ret = max(ret, maxLen(x, D1));  
36.         ret = max(ret, maxLen(y, D1));  
37.         ret = max(ret, maxLen(md, D2));  
38.         ret = max(ret, maxLen(cd, D2));  
39.   
40.         return ret;  
41.     }  
42. };  

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

class PowerSupply {
    int maxLen(vector<int> x, long long len) {
        int ret = 0;

        sort(x.begin(), x.end());
        REP(i, x.size()) {
            FOR (j, i, x.size()) {
                long long diff = x[j] - x[i];
                diff *= diff;
                if (diff <= len)
                    ret = max(ret, j-i+1);
            }
        }

        return ret;
    }

public:
    int maxProfit(vector<int> x, vector<int> y, int D) {
        int ret = 0;
        int N = x.size();

        vector<int> md = x;
        vector<int> cd = x;

        REP(i, N) md[i] = x[i] + y[i];
        REP(i, N) cd[i] = x[i] - y[i];

        long long D1 = 4LL * D * D;           // orthogonal
        long long D2 = 8LL * D * D;              // diagonal

        ret = max(ret, maxLen(x, D1));
        ret = max(ret, maxLen(y, D1));
        ret = max(ret, maxLen(md, D2));
        ret = max(ret, maxLen(cd, D2));

        return ret;
    }
};