QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#815173#9880. Origami Warpucup-team3734#WA 0ms3664kbC++233.6kb2024-12-15 06:26:442024-12-15 06:26:46

Judging History

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

  • [2024-12-15 06:26:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3664kb
  • [2024-12-15 06:26:44]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) (x).begin(), (x).end()
#define x first
#define y second

using pt = pair<ll, ll>;

pt operator-(const pt &lhs, const pt &rhs) {
  return pt{lhs.x - rhs.x, lhs.y - rhs.y};
}

ll norm(const pt &p) {
  return p.x * p.x + p.y * p.y;
}

pt read_pt() {
  pt res;
  cin >> res.x >> res.y;
  return res;
}

ll gcd(ll x, ll y) {
  x = abs(x);
  y = abs(y);
  while (x) {
    y %= x;
    swap(x, y);
  }
  return y;
}

struct Line {
  pt a, b;

  void normalize() {
    b = a - dir();
  }

  pt dir() const {
    pt d = a - b;
    ll g = gcd(d.x, d.y);
    d.x /= g;
    d.y /= g;

    if (d.x < 0) {
      d.x *= -1;
      d.y *= -1;
    }

    if (d.x == 0 && d.y < 0) {
      d.y *= -1;
    }

    return d;
  }

  ll type() const {
    pt d = dir();
    if (d == pt{1, 0})
      return 0;
    else if (d == pt{0, 1})
      return 1;
    else if (d == pt{1, 1})
      return 2;
    else if (d == pt{1, -1})
      return 3;
    else
      return 4;
  }

  ll ord() const {
    int t = type();
    assert(t < 4);

    if (t == 0)
      return a.y;

    if (t == 1)
      return a.x;

    if (t == 2)
      return a.x - a.y;

    if (t == 3)
      return a.x + a.y;
  }

  bool have_origin() const {
    return a.x * b.y - a.y * b.x == 0;
  }

  pt sym(const pt &p) const {
    assert(type() < 4);
    pt d = b - a;
    ll d_norm = norm(d);
    pt ap = p - a;
    ll proj_scalar = (ap.x * d.x + ap.y * d.y);
    pt nearest = {2 * a.x + 2 * d.x * proj_scalar / d_norm, 2 * a.y + 2 * d.y * proj_scalar / d_norm};
    return {nearest.x - p.x, nearest.y - p.y};
  }
};

Line read_line() {
  Line res;
  res.a = read_pt();
  res.b = read_pt();
  return res;
}

int n;
vector<Line> ls[5];
vector<ll> ds[5];
ll g[5], common_g;
bool all_origin;

void read() {
  for (int i = 0; i < 5; ++i) {
    ls[i].clear();
    ds[i].clear();
    g[i] = 0;
  }
  common_g = 0;
  all_origin = true;

  cin >> n;
  for (int i = 0; i < n; ++i) {
    auto l = read_line();
    l.normalize();
    ls[l.type()].push_back(l);

    all_origin &= l.have_origin();

    if (l.type() < 4)
      ds[l.type()].push_back(l.ord());
  }

  for (int i = 0; i < 4; ++i)
    if (ls[i].size() >= 2) {
      for (int j = 0; j + 1 < ls[i].size(); ++j)
        g[i] = gcd(g[i], (i < 2 ? 2 : 1) * (ls[i][j].ord() - ls[i][j + 1].ord()));
    }

  for (int i = 0; i < 4; ++i)
    common_g = gcd(common_g, g[i]);
}

int bit(int mask, int k) {
  return (mask >> k) & 1;
}

bool comp(ll x, ll g) {
  if (g == 0)
    return x == 0;
  return x % g == 0;
}

bool is_reachable(pt a, pt b) {
  if (!ls[4].empty()) {
    if (all_origin) {
      return norm(a) == norm(b);
    } else {
      return true;
    }
  }

  if ((a.x + a.y + b.x + b.y) % 2 != 0)
    return false;

  for (int mask = 0; mask < 16; ++mask) {
    pt cur = a;
    for (int k = 0; k < 4; ++k)
      if (bit(mask, k) && !ls[k].empty())
        cur = ls[k].front().sym(cur);

    pt diff = b - cur;

    if (ls[2].empty() && ls[3].empty()) {
      if (comp(diff.x, g[0]) && comp(diff.y, g[1]))
        return true;
    } else {
      if (comp(diff.x, common_g) && comp(diff.y, common_g))
        return true;
    }
  }

  return false;
}

void solve() {
  int q;
  cin >> q;
  while (q--) {
    pt a = read_pt();
    pt b = read_pt();

    cout << (is_reachable(a, b) ? "Yes" : "No") << "\n";
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("f.txt", "r", stdin);
#endif
  ios_base::sync_with_stdio(false);

  pt A{4, 0};
  pt B{0, 4};
  Line l{A, B};

  pt C{0, 1};

  auto S = l.sym(C);
  cout << S.x << " " << S.y << "\n";
  return 0;


  int t;
  cin >> t;
  while (t--) {
    read();
    solve();
  }

  return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3664kb

input:

2
3
0 0 1 0
0 0 0 1
0 2 2 0
4
1 0 2 3
1 -2 -1 2
1 1 -1 0
3 3 3 3
3
0 0 1 0
0 0 0 1
-2 1 2 3
2
2 1 -1 5
-1 -1 3 3

output:

3 4

result:

wrong output format YES or NO expected, but 3 found [1st token]