QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#815173 | #9880. Origami Warp | ucup-team3734# | WA | 0ms | 3664kb | C++23 | 3.6kb | 2024-12-15 06:26:44 | 2024-12-15 06:26:46 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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]