結果

問題 No.3005 トレミーの問題
ユーザー haihamabossu
提出日時 2025-01-17 23:28:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,879 bytes
コンパイル時間 2,261 ms
コンパイル使用メモリ 205,996 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-17 23:28:09
合計ジャッジ時間 3,528 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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) {
    rep(j, 3) {
      ll i0 = (i + j) % 4;
      ll i1 = (i + j + 1) % 4;
      ll i2 = (i + j + 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