ICPCアジア地区つくば大会2017 B問題 : Parallel Lines

問題. Parallel Lines

2次元平面上に 個の点がある．どの点もちょうど1つの対に含まれるように，すべての点から 個の対を作ることを考える．ここで，各対を対に含まれる2点を通る直線として考えると，いくつかの平行な直線に分割される．その分割の各部分の要素数を としたとき， の最大値を求めよ．

制約：

解法. 全探索

ペアの選び方を全探索する．まだ選ばれていない点(添字が小さいもの)を任意に選び，その対となるものを全通り試すということを順番に行うと，計算時間は下のような式になり間に合う．また，固定する点を選ばれていない点で最小の添字のものとすると探索空間は小さくなる．

計算時間 : 最悪の場合 　

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using Number = double;
const Number EPS = 1e-10;

inline int sign(Number x) { return (x < -EPS) ? -1 : (x > EPS) ? +1 : 0; }
inline bool equal(Number a, Number b) { return sign(a - b) == 0; }

class Point {
public:
    Number x, y;

    Point() {}
    Point(Number x, Number y) : x(x), y(y) {}

    Point operator-(const Point &rhs) const {
        return Point(this->x - rhs.x, this->y - rhs.y);
    }
};

inline Number abs_cross(const Point &p1, const Point &p2) {
    return p1.x * p2.y - p1.y * p2.x;
}

class Line : public std::array<Point, 2> {
public:
    Line() {}
    Line(const Point &p1, const Point &p2) {
        (*this)[0] = p1; (*this)[1] = p2;
    }
};
inline bool IsParallel(const Line &l1, const Line &l2) {
    return equal(abs_cross(l1[0] - l1[1], l2[0] - l2[1]), 0.0);
}

int Search(const int i, const int m, vector<int> &idx, const vector<Point> &p) {
    if (i == m - 2) {
        int sum = 0;
        vector<bool> check(m / 2, false);

        for (int j = 0; 2 * j < m; ++j) {
            if (check[j]) continue;

            check[j] = true;
            int num = 1;
            Line l(p[idx[2 * j]], p[idx[2 * j + 1]]);
            for (int k = j + 1; 2 * k < m; ++k)
                if (IsParallel(l, Line(p[idx[2 * k]], p[idx[2 * k + 1]]))) {
                    ++num;
                    check[k] = true;
                }
            sum += num * (num - 1) / 2;
        }
        return sum;
    }

    int res = 0;
    for (int j = i + 1; j < m; ++j) {
        swap(idx[i + 1], idx[j]);
        res = max(res, Search(i + 2, m, idx, p));
        swap(idx[i + 1], idx[j]);
    }

    return res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int m;

    cin >> m;
    vector<Point> p(m);
    for (auto &pp : p) cin >> pp.x >> pp.y;

    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);

    cout << Search(0, m, idx, p) << endl;

    return 0;
}

まとめ

方針から実装までに時間がかかった．

参考文献

[1] 審判長講評 : ICPC2017アジア地区つくば大会 B問題