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
外接円の中心の座標を として,次の方程式を解く.
つまり,次のような連立方程式を解けばよい.
解は次のようになる.
外接円の半径 は外接円の中心と 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 は若干異なるから注意すべし.
正規言語のポンピング補題
言語 が正規言語ならば,以下の条件を満たす自然数 (ポンピング長) が存在する.
任意の に対して ならば,以下の条件を満たすように と分割できる.
- 任意の *2 に対して
文脈自由文法のポンピング補題
言語 が文脈自由文法ならば,以下の条件を満たす自然数 (ポンピング長) が存在する.
任意の に対して ならば,以下の条件を満たすように と分割できる.
- 任意の に対して