結果

問題 No.3005 トレミーの問題
コンテスト
ユーザー haihamabossu
提出日時 2025-02-11 01:21:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,876 bytes
コンパイル時間 10,010 ms
コンパイル使用メモリ 423,280 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-11 01:22:03
合計ジャッジ時間 10,268 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
using namespace std;
using ll = long long;
using R = boost::rational<boost::multiprecision::cpp_int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

template <typename T> void gaussian_elimination(vector<vector<T>> &mat) {
  int n = mat.size(), m = mat[0].size();
  int p = -1;
  for (int j = 0; j < m; j++) {
    bool found = false;
    for (int i = p + 1; i < n; i++) {
      if (mat[i][j] != 0) {
        found = true;
        p += 1;
        if (p < i) {
          swap(mat[p], mat[i]);
        }
        break;
      }
    }
    if (!found) {
      continue;
    }
    for (int j2 = m - 1; j2 >= j; j2--) {
      mat[p][j2] /= mat[p][j];
    }
    for (int i = 0; i < n; i++) {
      if (i == p) {
        continue;
      }
      for (int j2 = m - 1; j2 >= j; j2--) {
        mat[i][j2] -= mat[p][j2] * mat[i][j];
      }
    }
  }
}

bool on_same_line(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
  if (x1 != 0 || y1 != 0) {
    return on_same_line(x1 - x1, y1 - y1, x2 - x1, y2 - y1, x3 - x1, y3 - y1);
  } else {
    return y2 * x3 == y3 * x2;
  }
}

void solve() {
  ll n = 4;
  vector<ll> xs(n), ys(n);
  rep(i, n) cin >> xs[i] >> ys[i];
  rep(i, n) {
    ll j = (i + 1) % n, k = (i + 2) % n;
    if (on_same_line(xs[i], ys[i], xs[j], ys[j], xs[k], ys[k])) {
      cout << "NO\n";
      return;
    }
  }
  vector mat(3, vector<R>(4));
  rep(i, n - 1) mat[i] = {xs[i], ys[i], 1, -(xs[i] * xs[i] + ys[i] * ys[i])};
  gaussian_elimination(mat);
  ll x = xs[n - 1], y = ys[n - 1];
  R res = x * x + y * y + mat[0].back() * x + mat[1].back() * y + mat[2].back();
  cout << (res == 0 ? "YES" : "NO") << '\n';
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  int T = 1;
  for (int t = 0; t < T; t++) {
    solve();
  }
  return 0;
}
0