AOJ 0012

A Point in a Triangle | Aizu Online Judge

外積を用いて判定します.

#include <iostream>
#include <array>

using namespace std;

class point {
public:
    double x, y;
    double operator%(const point &p) const;
    point operator-(const point &p) const;
};

// cross product
double point::operator%(const point &p) const {
    return this->x * p.y - this->y * p.x;
}

point point::operator-(const point &p) const {
    point r;
    r.x = this->x - p.x;
    r.y = this->y - p.y;
    return r;
}

int main() {
    array<point, 4> p;
    while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y >> p[3].x >> p[3].y) {
        double c0 = (p[2] - p[0]) % (p[0] - p[3]);
        double c1 = (p[0] - p[1]) % (p[1] - p[3]);
        double c2 = (p[1] - p[2]) % (p[2] - p[3]);

        if ((c0 > 0 && c1 > 0 && c2 > 0) || (c0 < 0 && c1 < 0 && c2 < 0)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

AOJ 0011

Drawing Lots | Aizu Online Judge

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int w, n;
    cin >> w;
    cin >> n;

    vector<int> lots(w);
    iota(lots.begin(), lots.end(), 1);

    for (int i = 0; i < n; ++i) {
        pair<int, int> p;
        cin >> p.first;
        cin.ignore();
        cin >> p.second;
        iter_swap(lots.begin() + p.first - 1, lots.begin() + p.second - 1);
    }

    for (auto l : lots) {
        cout << l << endl;
    }

    return 0;
}

AOJ 0010

Circumscribed Circle of a Triangle | Aizu Online Judge

外接円の中心の座標を  \mathrm{O}(x, y) として,次の方程式を解く.

 \displaystyle (x-x_1)^2 + (y-y_1)^2 = (x-x_2)^2 + (y-y_2)^2 = (x-x_3)^2 + (y-y_3)^2

つまり,次のような連立方程式を解けばよい.

 \displaystyle \left\{ \begin{array}{l} (x-x_1)^2 + (y-y_1)^2 = (x-x_2)^2 + (y-y_2)^2 \\ (x-x_2)^2 + (y-y_2)^2 = (x-x_3)^2 + (y-y_3)^2 \end{array} \right.

解は次のようになる.

 \displaystyle x = \frac{1}{2} \frac{(y_3-y_2)(x_2^2-x_1^2+y_2^2-y_1^2) - (y_2-y_1)(x_3^2-x_2^2+y_3^2-y_2^2)}{(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)}

 \displaystyle y = \frac{1}{2} \frac{-(x_3-x_2)(x_2^2-x_1^2+y_2^2-y_1^2) + (x_2-x_1)(x_3^2-x_2^2+y_3^2-y_2^2)}{(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)}

外接円の半径  r は外接円の中心と 3 つのうちのひとつの点の Euclid 距離を求めればいい.

#include <iostream>
#include <array>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        array<pair<double, double>, 3> p;
        cin >> p[0].first >> p[0].second >> p[1].first >> p[1].second >> p[2].first >> p[2].second;

        pair<long double, long double> o(
                ((p[2].second - p[1].second) * (pow(p[1].first, 2.0) - pow(p[0].first, 2.0) + pow(p[1].second, 2.0) - pow(p[0].second, 2.0)) - (p[1].second - p[0].second) * (pow(p[2].first, 2.0) - pow(p[1].first, 2.0) + pow(p[2].second, 2.0) - pow(p[1].second, 2.0))) / (2.0 * ((p[1].first - p[0].first) * (p[2].second - p[1].second) - (p[1].second - p[0].second) * (p[2].first - p[1].first))),
                (- (p[2].first - p[1].first) * (pow(p[1].first, 2.0) - pow(p[0].first, 2.0) + pow(p[1].second, 2.0) - pow(p[0].second, 2.0)) + (p[1].first - p[0].first) * (pow(p[2].first, 2.0) - pow(p[1].first, 2.0) + pow(p[2].second, 2.0) - pow(p[1].second, 2.0))) / (2.0 * ((p[1].first - p[0].first) * (p[2].second - p[1].second) - (p[1].second - p[0].second) * (p[2].first - p[1].first)))
        );

        long double r = sqrt(pow(p[0].first - o.first, 2.0) + pow(p[0].second - o.second, 2.0));

        cout << fixed << setprecision(3) << o.first << " " << o.second << " " << r << endl;
    }

    return 0;
}

AOJ 0009

Prime Number | Aizu Online Judge

普通に Eratosthenes の篩を用いる.実行時に素数を数えるより,予め計算しておいたほうがはやい.

#include <iostream>
#include <array>

using namespace std;

int main() {
    const int N = 1000000;

    array<bool, N> search_array;
    array<int, N> count_array;

    search_array.fill(true);
    search_array[0] = false;
    search_array[1] = false;

    for (int i = 2; i < N; ++i) {
        // Sieve of Eratosthenes
        if (search_array[i]) {
            for (int j = 2; i * j < N; ++j) {
                search_array[i * j] = false;
            }
        }

        // count prime numbers
        count_array[i] = count_array[i - 1] + search_array[i];
    }

    int n;
    while (cin >> n) {
        cout << count_array[n] << endl;
    }

    return 0;
}

ポンピング補題の証明問題

反復補題 (pumping lemma) はある言語が正規言語や文脈自由文法でないことを示すときに使う定理である. 正規言語に対する反復補題と文脈自由文法に対する反復補題 *1 は若干異なるから注意すべし.

正規言語のポンピング補題

言語  L が正規言語ならば,以下の条件を満たす自然数  p (ポンピング長) が存在する.

任意の  \sigma \in L に対して  |\sigma| \geq p ならば,以下の条件を満たすように  \sigma = \alpha \beta \gamma と分割できる.

  1.  |\alpha \beta| \leq p
  2.  |\beta| > 0
  3. 任意の  n \in \mathbb{N} *2 に対して  \alpha \beta^n \gamma \in L

文脈自由文法のポンピング補題

言語  L が文脈自由文法ならば,以下の条件を満たす自然数  p (ポンピング長) が存在する.

任意の  \sigma \in L に対して  |\sigma| \geq p ならば,以下の条件を満たすように  \sigma = uvwxy と分割できる.

  1.  |vwx| \leq p
  2.  |vx| > 0
  3. 任意の  n \in \mathbb{N} に対して  uv^nwx^ny \in L

*1: uvwxy 定理と呼ばれたりする.

*2: \mathbb{N} はゼロを含む自然数の集合とする.

続きを読む

院試受験記 (JAIST)

今日は JAIST の第 1 回博士前期課程入学試験を受験してきた。

国立大の情報系学科に通う B4 というパンピーの話ですが、今後受験する人たちの参考になればと思います。

続きを読む