QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125230#6734. Click the Circlehos_lyricWA 7ms3840kbC++147.7kb2023-07-16 07:54:462023-07-16 07:54:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 07:54:50]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3840kb
  • [2023-07-16 07:54:46]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
struct Pt {
  Int x, y;
  Pt() : x(0), y(0) {}
  Pt(Int x_, Int y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
  Int abs2() const { return x * x + y * y; }
  Int dot(const Pt &a) const { return x * a.x + y * a.y; }
  Int det(const Pt &a) const { return x * a.y - y * a.x; }
  bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
  bool operator<(const Pt &a) const { return (x < a.x || (x == a.x && y < a.y)); }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

// Watch out for the case a == b.
int iSP(const Pt &a, const Pt &b, const Pt &c) {
  int s = sig((b - a).det(c - a));
  if (s) return s;
  if (sig((b - a).dot(c - a)) < 0) return -2; // c-a-b
  if (sig((a - b).dot(c - b)) < 0) return +2; //   a-b-c
  return 0;
}
// Watch out for the case a == b || c == d.
bool iSS(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
  return (iSP(a, b, c) * iSP(a, b, d) <= 0 && iSP(c, d, a) * iSP(c, d, b) <= 0);
}



int N;
Int R, W;
vector<int> O;
vector<Pt> C, D;
vector<Int> U, V;

struct Info {
  int len;
  Int ts[4];
  Pt ps[4];
};

bool dSP2(const Pt &a, const Pt &b, const Pt &c) {
	if ((b - a).dot(c - a) <= 0) return (c - a).abs2() <=4*R*R;
	if ((a - b).dot(c - b) <= 0) return (c - b).abs2() <=4*R*R;
	// return abs(tri(a, b, c)) / (b - a).abs();
// cerr<<"  HELP "<<tri(a, b, c)<<" "<<(b - a).abs2()<<endl;
  return tri(a, b, c) * tri(a, b, c) <= 4*R*R * (b - a).abs2();
}
bool dSS2(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
	return iSS(a, b, c, d) ? true : max(max(dSP2(a, b, c), dSP2(a, b, d)), max(dSP2(c, d, a), dSP2(c, d, b)));
}

bool solve(const Pt c0, const Pt &u0, Int d0, const Pt &c1, const Pt &u1, Int d1, Int tL, Int tR) {
// cerr<<"  solve "<<c0<<" "<<u0<<" "<<d0<<" "<<c1<<" "<<u1<<" "<<d1<<" "<<tL<<" "<<tR<<endl;
  __int128 tar = 4*R*R;
  tar *= d0*d0;
  tar *= d1*d1;
  const Pt o = d0 * c1 - d1 * c0;
  const Pt u = d0 * u1 - d1 * u0;
  // a t^2 + 2 b t + c <= 0
  __int128 a = (__int128)u.x * u.x + (__int128)u.y * u.y;
  __int128 b = (__int128)u.x * o.x + (__int128)u.y * o.y;
  __int128 c = (__int128)o.x * o.x + (__int128)o.y * o.y;
  c -= tar;
  if ((a * tL + 2*b) * tL + c <= 0) return true;
  if ((a * tR + 2*b) * tR + c <= 0) return true;
  if (a > 0 && b*b - a*c >= 0 && a*tL <= -b && -b <= a*tR) return true;
  return false;
}

bool segseg(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
// cerr<<"  segseg "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
  if (a == b && c == d) {
    return ((c - a).abs2() <= 4*R*R);
  } else if (a == b) {
    return dSP2(c, d, a);
  } else if (c == d) {
    return dSP2(a, b, c);
  } else {
    return dSS2(a, b, c, d);
  }
}

bool circir(const Info &c0, const Info &c1) {
  for (int i0 = 0; i0 < c0.len; ++i0) for (int i1 = 0; i1 < c1.len; ++i1) {
    const Int tL = max(c0.ts[i0], c1.ts[i1]);
    const Int tR = min(c0.ts[i0 + 1], c1.ts[i1 + 1]);
    if (tL <= tR) {
// cerr<<"  help "<<i0<<" "<<i1<<" "<<tL<<" "<<tR<<endl;
      const Int d0 = c0.ts[i0 + 1] - c0.ts[i0];
      const Int d1 = c1.ts[i1 + 1] - c1.ts[i1];
      const Pt u0 = c0.ps[i0 + 1] - c0.ps[i0];
      const Pt u1 = c1.ps[i1 + 1] - c1.ps[i1];
      if (solve(
          d0 * c0.ps[i0] - c0.ts[i0] * u0, u0, d0,
          d1 * c1.ps[i1] - c1.ts[i1] * u1, u1, d1,
          tL, tR)) {
        return true;
      }
    }
  }
  return false;
}
bool fracir(const Info &f, const Info &c) {
  if (max(f.ts[0], c.ts[0]) <= min(f.ts[1], c.ts[c.len])) {
    if (segseg(f.ps[0], f.ps[1], c.ps[0], c.ps[c.len])) {
      return true;
    }
  }
  return false;
}
bool frafra(const Info &f0, const Info &f1) {
  if (max(f0.ts[0], f1.ts[0]) <= min(f0.ts[1], f1.ts[1])) {
    if (segseg(f0.ps[0], f0.ps[1], f1.ps[0], f1.ps[1])) {
      return true;
    }
  }
  return false;
}

int main() {
  for (; ~scanf("%d%lld%lld", &N, &R, &W); ) {
    O.resize(N);
    C.resize(N);
    D.resize(N);
    U.resize(N);
    V.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &O[i]);
      if (O[i] == 1) {
        scanf("%lld%lld%lld", &C[i].x, &C[i].y, &U[i]);
      } else {
        scanf("%lld%lld%lld%lld%lld%lld", &C[i].x, &C[i].y, &D[i].x, &D[i].y, &U[i], &V[i]);
      }
    }
    
    vector<Info> circles, frames;
    for (int i = 0; i < N; ++i) {
      if (O[i] == 1) {
        Info c;
        c.len = 1;
        c.ts[0] = U[i] - W;
        c.ts[1] = U[i] + W;
        c.ps[0] = C[i];
        c.ps[1] = C[i];
        circles.push_back(c);
      } else {
        Info c, f;
        c.len = 3;
        c.ts[0] = U[i] - W;
        c.ts[1] = U[i];
        c.ts[2] = V[i];
        c.ts[3] = V[i] + W;
        c.ps[0] = C[i];
        c.ps[1] = C[i];
        c.ps[2] = D[i];
        c.ps[3] = D[i];
        circles.push_back(c);
        f.len = 1;
        f.ts[0] = U[i] - W;
        f.ts[1] = V[i] + W;
        f.ps[0] = C[i];
        f.ps[1] = D[i];
        frames.push_back(f);
      }
    }
    
    int ans = 0;
    for (int i = 0; i < (int)circles.size(); ++i) for (int j = i + 1; j < (int)circles.size(); ++j) {
      if (circir(circles[i], circles[j])) {
// cerr<<"circir "<<i<<" "<<j<<endl;
        ++ans;
      }
    }
    for (int i = 0; i < (int)frames.size(); ++i) for (int j = 0; j < (int)circles.size(); ++j) {
      if (fracir(frames[i], circles[j])) {
// cerr<<"fracir "<<i<<" "<<j<<endl;
        ++ans;
      }
    }
    for (int i = 0; i < (int)frames.size(); ++i) for (int j = i + 1; j < (int)frames.size(); ++j) {
      if (frafra(frames[i], frames[j])) {
// cerr<<"frafra "<<i<<" "<<j<<endl;
        ++ans;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

2 1 1
1 1 1 2
1 2 2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

2 1 1
1 1 1 2
1 3 2 3

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

2 1 1
1 3 3 2
2 5 5 5 1 2 4

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

2 1 1
2 1 1 1 5 2 4
2 5 5 5 1 2 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

2 1 1
2 10 1 10 20 2 4
2 1 10 20 10 2 4

output:

6

result:

ok 1 number(s): "6"

Test #6:

score: -100
Wrong Answer
time: 7ms
memory: 3840kb

input:

1000 8 4
1 8323 2820 943
1 8246 2850 944
1 8177 2880 941
1 8154 2866 944
2 8325 8146 2865 2846 943 944
1 8349 2891 939
2 8176 8344 2888 2692 940 945
1 8191 2732 945
1 8144 2668 945
2 8182 8191 2889 2844 939 940
1 8173 2687 941
1 8241 2870 945
2 8266 8344 2910 2667 942 943
1 8169 2863 939
1 8349 2921...

output:

28635

result:

wrong answer 1st numbers differ - expected: '22721', found: '28635'