結果

問題 No.2602 Real Collider
コンテスト
ユーザー amentorimaru
提出日時 2023-11-21 21:24:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 2,382 bytes
コンパイル時間 1,071 ms
コンパイル使用メモリ 78,976 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 07:20:04
合計ジャッジ時間 17,225 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 78
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>


using namespace std;
using ll = long long;

ll calcCrossProduct(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
  return x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1;
}

// <
bool compareRational(ll n1, ll d1, ll n2, ll d2) {
  if (d1 == 0)
    return false;
  if (d2 == 0)
    return n2 != 0;
  if (n1 / d1 != n2 / d2)
    return n1 / d1 < n2 / d2;
  return compareRational(d2, n2 % d2, d1, n1 % d1);
}

int main() {
  ll q;
  ll xa, ya, xb, yb, xc, yc;
  cin >> q >> xa >> ya >> xb >> yb >> xc >> yc;
  ll sqa = (xb - xc) * (xb - xc) + (yb - yc) * (yb - yc);
  ll sqb = (xc - xa) * (xc - xa) + (yc - ya) * (yc - ya);
  ll sqc = (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
  if (sqb >= sqa && sqb >= sqc) {
    swap(xa, xb);
    swap(ya, yb);
  }
  else if (sqc >= sqa && sqc >= sqb) {
    swap(xa, xc);
    swap(ya, yc);
  }
  sqa = (xb - xc) * (xb - xc) + (yb - yc) * (yb - yc);
  sqb = (xc - xa) * (xc - xa) + (yc - ya) * (yc - ya);
  sqc = (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);

  if (sqa >= sqb + sqc) {
    for (ll i = 0; i < q; i++) {
      ll x, y;
      cin >> x >> y;
      ll bd = (xb - x) * (xb - x) + (yb - y) * (yb - y);
      ll cd = (xc - x) * (xc - x) + (yc - y) * (yc - y);
      if (bd + cd <= sqa)
        cout << "Yes\n";
      else 
        cout << "No\n";
    }
  }
  else {
    ll area = calcCrossProduct(xb, yb, xc, yc, xa, ya);
    ll cosSquNum = (xb - xa) * (xc - xa) + (yb - ya) * (yc - ya);
    cosSquNum *= cosSquNum;
    ll cosSquDem = sqb * sqc;
    for (ll i = 0; i < q; i++) {
      ll x, y;
      cin >> x >> y;
      ll bd = (xb - x) * (xb - x) + (yb - y) * (yb - y);
      ll cd = (xc - x) * (xc - x) + (yc - y) * (yc - y);
      ll inner = (xb - x) * (xc - x) + (yb - y) * (yc - y);
      ll cosSquNumi = inner * inner;
      ll cosSquDemi = bd * cd;
      ll areai = calcCrossProduct(xb, yb, xc, yc, x, y);
      if (area * areai >= 0) {
        if (inner < 0 || !compareRational(cosSquNum, cosSquDem, cosSquNumi, cosSquDemi)) {          
          cout << "Yes\n";
        }
        else {
          cout << "No\n";
        }
      }
      else {
        if (inner > 0) {
          cout << "No\n";
        }
        else if (!compareRational(cosSquNumi, cosSquDemi, cosSquNum, cosSquDem)) {
          cout << "Yes\n";
        }
        else {
          cout << "No\n";
        }
      }
    }
  }
}
0