SRM 466 DIV 2とPKU 3668 Game of Lines - div1に上がりたいkeitanxkeitanの日記

topcoderはエントリーを開始時間５分前までにする必要がある。

よし。もう忘れない。
ということで参加はしていない。後日取り組んでみよう。



座標平面上の格子点(-1,000 <= x <= 1,000, -1,000 <= y <= 1,000)に

N個の点が打たれている(2 <= N <= 1,000)。

点を繋いで直線を引いて１点得ることができるが、平行な直線を引くことはできない。

点をいくつかの直線で共有するのはあり。

得点の最大値は？

方針



どんな引き方をすればいいの？とは聞いてきていない。

…というところから考えてもわかるように、同じ傾きをもつ直線が何本か引けるとして、

どちらを選ぶのがベターということはない。なぜなら複数の直線で点を共有できるから。

つまりこの問題は点を繋いで作れる直線の傾きは何通りありますか？

という風に読み替えることができる。

全部でnC2本の直線が引けるので各傾きを計算してsetに格納してset.size()を出力して終了！
と思ったけど、いくつか詰まったのでメモ。



1. 傾き∞(-∞)を考慮していなかったので0割りが発生。問題の性質上∞と-∞は同じ扱い。

2. 傾きをdoubleで計算していたが、誤差により「同じ」とみなされなかった傾きがあった。

   （分数の約分）

結局傾きのために分数クラス作って、約分して整数の組として保存した。

#include<cstdio>
#include<vector>
#include<set>
#include<climits>

using namespace std;

int calcgcd(int a, int b) {
    if (a < b) {
        int c = a; a = b; b = c;
    }
    while (b > 0) {
        int c = a % b;
        if (c == 0) break;
        a = b;
        b = c;
    }
    return b;
}

int myabs(int a) {
    return a>=0?a:-a;
}

struct Frac {
    int d, n;
    Frac (int arg_d, int arg_n) {
        if (arg_d == 0) { // 分母が0だから傾き無限大
            d = 1;
            n = INT_MAX;
        } else if (arg_n == 0) { // 分子が0だから傾き0
            d = 1;
            n = 0;
        } else {
            int sign = 1;
            if (arg_d * arg_n < 0) sign = -1;
            arg_d = myabs(arg_d); arg_n = myabs(arg_n);
            int gcd = calcgcd(arg_d, arg_n);
            d = arg_d / gcd;
            n = sign * arg_n / gcd; // 負号は分子につける
        }
    }
    bool operator < (const Frac &frac) const { // setに格納するには<が必要
        return (double)n/(double)d < (double)frac.n/(double)frac.d;
    }
};

struct Point {
    int x, y;
    Point() {}
    Point(int x, int y) :
        x(x), y(y) {}
    Frac calcGrad(const Point &p) const {
        return Frac(x - p.x, y - p.y);
    }
};

int main() {
    int N;
    scanf("%d", &N);
    vector<Point> ps(N);
    for (int i = 0; i < N; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        ps[i] = Point(x, y);
    }
    set<Frac> grads;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            grads.insert(ps[i].calcGrad(ps[j]));
        }
    }
    printf("%d\n", grads.size());
}

id:mickey24さん、id:halwhiteの教えにより、setに自作クラスを格納する場合の比較関数は<であることがわかった。
setは内部でsortをしてデータを保持しているため、<が必要。==となる条件は!(a

次のコードは、傾きA, Bがあったら、
(Aのdy)×(Bのdx) ＝ (Bのdy)×(Aのdx)
ならばAとBは等しいということを利用したコードのつもりなんだけど欠陥があるらしくサンプル入力で間違えてしまう。
謎。

#include<cstdio>
#include<vector>
#include<set>

using namespace std;

struct Grad {
    int dx, dy;
    Grad(int dx, int dy) :
        dx(dx), dy(dy) {}
    bool operator < (const Grad &grad) const {
        return dx * grad.dy < grad.dx * dy;
    }
};

struct Point {
    int x, y;
    Point () {}
    Point (int x, int y) :
        x(x), y(y) {}
    Grad calcGrad(const Point &p) const {
        return Grad(x - p.x, y - p.y);
    }
};

int main() {
    int N;
    scanf("%d", &N);
    vector<Point> ps(N);
    for (int i = 0; i < N; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        ps[i] = Point(x, y);
    }
    set<Grad> grads;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            grads.insert(ps[i].calcGrad(ps[j]));
        }
    }
    printf("%d\n", grads.size());
}