#943965 (C++17) No.2602 Real Collider

提出ソース

結果

問題	No.2602 Real Collider
ユーザー	maeshun
提出日時	2024-01-13 13:40:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,928 bytes
コンパイル時間	4,674 ms
コンパイル使用メモリ	265,836 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-28 01:22:14
合計ジャッジ時間	15,417 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	338 ms 5,376 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	AC	45 ms 5,376 KB
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for(int i=0;i<(n);++i)
#define rep1(i, n) for(int i=1;i<=(n);i++)
#define ll long long
using mint = modint998244353;
using P = pair<ll,ll>;
using lb = long double;
using T = tuple<ll, ll, ll>;
#ifdef LOCAL
#  include <debug_print.hpp>
#  define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define dbg(...) (static_cast<void>(0))
#endif

template<typename T>
struct Matrix {
  int h, w;
  vector<vector<T>> d;
  Matrix() {}
  //初期化のときは Matrix<> a(h, w)
  Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}
  Matrix& unit() {
    assert(h == w);
    rep(i,h) d[i][i] = 1;
    return *this;
  }
  const vector<T>& operator[](int i) const { return d[i];}
  vector<T>& operator[](int i) { return d[i];}
  Matrix operator*(const Matrix& a) const {
    assert(w == a.h);
    Matrix r(h, a.w);
    rep(i,h)rep(k,w)rep(j,a.w) {
      r[i][j] += d[i][k]*a[k][j];
    }
    return r;
  }
  //Matcix<> newa = a.pow(k)と使う
  Matrix pow(long long t) const {
    assert(h == w);
    if (!t) return Matrix(h,h).unit();
    if (t == 1) return *this;
    Matrix r = pow(t>>1);
    r = r*r;
    if (t&1) r = r*(*this);
    return r;
  }
};

// Vector
// https://youtu.be/UWbGRhF3Ozw?t=9564
long double eps = 1e-12;
struct V {
  long double x, y;
  V(long double x=0, long double y=0): x(x), y(y) {}
  V& operator+=(const V& v) { x += v.x; y += v.y; return *this;}
  V operator+(const V& v) const { return V(*this) += v;}
  V& operator-=(const V& v) { x -= v.x; y -= v.y; return *this;}
  V operator-(const V& v) const { return V(*this) -= v;}
  V& operator*=(long double s) { x *= s; y *= s; return *this;}
  V operator*(long double s) const { return V(*this) *= s;}
  V& operator/=(long double s) { x /= s; y /= s; return *this;}
  V operator/(long double s) const { return V(*this) /= s;}
  long double dot(const V& v) const { return x*v.x + y*v.y;}
  long double cross(const V& v) const { return x*v.y - v.x*y;}
  long double norm2() const { return x*x + y*y;}
  long double norm() const { return sqrt(norm2());}
  V normalize() const { return *this/norm();}
  V rotate90() const { return V(y, -x);}
  int ort() const { // orthant
    if (abs(x) < eps && abs(y) < eps) return 0;
    if (y > 0) return x>0 ? 1 : 2;
    else return x>0 ? 4 : 3;
  }
  bool operator<(const V& v) const {
    int o = ort(), vo = v.ort();
    if (o != vo) return o < vo;
    return cross(v) > 0;
  }
};
istream& operator>>(istream& is, V& v) {
  is >> v.x >> v.y; return is;
}
ostream& operator<<(ostream& os, const V& v) {
  os<<"("<<v.x<<","<<v.y<<")"; return os;
}

//三点の外心、一直線の時{1e18,1e18}
V circumcenter(V &P1, V &P2, V &P3){
    V P12 = P2 - P1;
    V P13 = P3 - P1;
    long double AB2 = P12.norm2();
    long double AC2 = P13.norm2();
    long double ABAC = P12.dot(P13);
    long double EPS = 1.0E-12;
    long double denominator = (AB2*AC2-ABAC*ABAC);
    V ans;
    if(denominator < EPS){
        // fprintf(stderr, "Circumcenter Error\n");
        return {1e18, 1e18};
    }
    long double x = 0.5*(AB2*AC2-AC2*ABAC)/denominator;
    long double y = 0.5*(AB2*AC2-AB2*ABAC)/denominator;
    ans = P12*x + P13*y + P1;
    return ans;
}


int main()
{
    int q;
    cin >> q;
    ll x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    ll r;
    if((x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)){
        ll Mx = max(x1, max(x2,x3));
        ll mx = min(x1, min(x2, x3));
        ll My = max(y1,max(y2, y3));
        ll my = min(y1,min(y2, y3));
        r = (Mx-mx) * (Mx-mx) + (My-my)*(My-my);
        ll xg = (mx+Mx);
        ll yg = (my+My);
        rep(i,q){
            ll x, y;
            cin >> x >> y;
            x *= 2 ;
            y *= 2 ;
            ll R = (xg-x)*(xg-x) + (yg-y) * (yg-y);
            if(R<=r) {
                cout << "Yes" << "\n";
            }
            else{
                cout << "No" << "\n";
            }
        }
    }
    else{
        ll det = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
        Matrix<ll> m(2,2);
        m[1][1] = x2-x1;
        m[0][1] = -y2+y1;
        m[0][0] = y3-y1;
        m[1][0] = -x3+x1;
        Matrix<ll> f(2,1);
        f[0][0] = x2*x2+y2*y2 - x1*x1-y1*y1;
        f[1][0] = x3*x3+y3*y3 - x1*x1-y1*y1;
        dbg(det);
        Matrix<ll> e = m*f;
        r = (e[0][0]-2*det*x1) * (e[0][0]-2*det*x1) + (e[1][0]-2*det*y1) * (e[1][0] - 2*det*y1);
        dbg(e[0][0], e[1][0]);
        dbg(r);
        rep(i,q){
            ll x, y;
            cin >> x >> y;
            x *= 2 *det;
            y *= 2 *det;
            ll R = (e[0][0]-x)*(e[0][0]-x) + (e[1][0]-y) * (e[1][0]-y);
            dbg(R);
            if(R<=r) {
                cout << "Yes" << "\n";
            }
            else{
                cout << "No" << "\n";
            }
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード