結果

問題 No.3005 トレミーの問題
ユーザー haihamabossu
提出日時 2025-01-17 23:30:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,841 bytes
コンパイル時間 2,665 ms
コンパイル使用メモリ 203,588 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-17 23:30:47
合計ジャッジ時間 3,619 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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;
  }
}

pair<ll, ll> calc_gcd(ll a, ll b) {
  if (a == 0 && b == 0) {
    return {0, 0};
  } else if (a == 0) {
    return {0, 1};
  } else if (b == 0) {
    return {1, 0};
  } else if (a < 0 && b < 0) {
    return calc_gcd(-a, -b);
  } else if (a < 0 || b < 0) {
    auto [ra, rb] = calc_gcd(abs(a), abs(b));
    return {-ra, rb};
  } else {
    ll g = __gcd(a, b);
    return {a / g, b / g};
  }
}

tuple<ll, ll, ll, ll> calc(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
  ll p1 = (x1 * x1 + y1 * y1) * (y2 - y3) + (x2 * x2 + y2 * y2) * (y3 - y1) +
          (x3 * x3 + y3 * y3) * (y1 - y2);
  ll p2 = (x1 - x2) * (y2 - y3) - (x2 * x3) * (y1 - y2);
  ll q1 = (x1 * x1 + y1 * y1) * (x2 - x3) + (x2 * x2 + y2 * y2) * (x3 - x1) +
          (x3 * x3 + y3 * y3) * (x1 - x2);
  ll q2 = (y1 - y2) * (x2 - x3) - (y2 * y3) * (x1 - x2);
  tie(p1, p2) = calc_gcd(p1, p2);
  tie(q1, q2) = calc_gcd(q1, q2);
  return {p1, p2, q1, q2};
}

void solve() {
  vector<ll> xs(4), ys(4);
  rep(i, 4) cin >> xs[i] >> ys[i];
  set<tuple<ll, ll, ll, ll>> st;
  bool ok = true;
  rep(i, 4) {
    ll i0 = (i + 0) % 4;
    ll i1 = (i + 1) % 4;
    ll i2 = (i + 2) % 4;
    ok &= !on_same_line(xs[i0], ys[i0], xs[i1], ys[i1], xs[i2], ys[i2]);
    st.insert(calc(xs[i0], ys[i0], xs[i1], ys[i1], xs[i2], ys[i2]));
  }
  ok &= st.size() == 1;
  cout << (ok ? "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