結果
| 問題 | No.2628 Shrinkage |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2024-02-16 21:25:41 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,430 bytes |
| コンパイル時間 | 3,042 ms |
| コンパイル使用メモリ | 261,004 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-09-28 19:42:57 |
| 合計ジャッジ時間 | 3,707 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| 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 | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
namespace geometry {
using Integer = long long;
int sgn(const Integer x) {
return x > 0 ? 1 : (x < 0 ? -1 : 0);
}
struct Point {
Integer x, y;
explicit Point(const Integer x = 0, const Integer y = 0) : x(x), y(y) {}
Integer norm() const { return x * x + y * y; }
Point& operator+=(const Point& p) {
x += p.x; y += p.y;
return *this;
}
Point& operator-=(const Point& p) {
x -= p.x; y -= p.y;
return *this;
}
Point& operator*=(const Integer k) {
x *= k; y *= k;
return *this;
}
Point& operator/=(const Integer k) {
x /= k; y /= k;
return *this;
}
std::strong_ordering operator<=>(const Point& p) const {
const int x_sgn = sgn(p.x - x);
if (x_sgn == 0) return 0 <=> sgn(p.y - y);
return x_sgn == 1 ? std::strong_ordering::less :
std::strong_ordering::greater;
}
Point operator+() const { return *this; }
Point operator-() const { return Point(-x, -y); }
Point operator+(const Point& p) const { return Point(*this) += p; }
Point operator-(const Point& p) const { return Point(*this) -= p; }
Point operator*(const Integer k) const { return Point(*this) *= k; }
Point operator/(const Integer k) const { return Point(*this) /= k; }
friend std::ostream& operator<<(std::ostream& os, const Point& p) {
return os << '(' << p.x << ", " << p.y << ')';
}
friend std::istream& operator>>(std::istream& is, Point& p) {
Integer x, y; is >> x >> y;
p = Point(x, y);
return is;
}
};
struct Segment {
Point s, t;
explicit Segment(const Point& s = Point(0, 0), const Point& t = Point(0, 0))
: s(s), t(t) {}
};
struct Line : Segment {
using Segment::Segment;
};
struct Circle {
Point p; Integer r;
explicit Circle(const Point& p = Point(0, 0), const Integer r = 0)
: p(p), r(r) {}
};
Integer cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
Integer dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }
int ccw(const Point& a, const Point& b, const Point& c) {
const Point ab = b - a, ac = c - a;
const int sign = sgn(cross(ab, ac));
if (sign == 0) {
if (sgn(dot(ab, ac)) == -1) return 2;
if (sgn(ac.norm() - ab.norm()) == 1) return -2;
}
return sign;
}
Integer closest_pair(std::vector<Point> ps) {
const int n = ps.size();
assert(n >= 2);
std::sort(ps.begin(), ps.end());
const auto f = [&ps](auto f, const int left, const int right) -> Integer {
const int mid = std::midpoint(left, right);
Integer x_mid = ps[mid].x, d = std::numeric_limits<Integer>::max();
if (left + 1 < mid) d = std::min(d, f(f, left, mid));
if (mid + 1 < right) d = std::min(d, f(f, mid, right));
std::inplace_merge(std::next(ps.begin(), left), std::next(ps.begin(), mid),
std::next(ps.begin(), right),
[](const Point& a, const Point& b) -> bool {
return sgn(b.y - a.y) == 1;
});
std::vector<Point> tmp;
for (int i = left; i < right; ++i) {
if (sgn((ps[i].x - x_mid) * (ps[i].x - x_mid) - d) == 1) continue;
for (int j = std::ssize(tmp) - 1; j >= 0; --j) {
const Point v = ps[i] - tmp[j];
if (sgn(v.y * v.y - d) == 1) break;
d = std::min(d, v.norm());
}
tmp.emplace_back(ps[i]);
}
return d;
};
return f(f, 0, n);
}
bool is_parallel(const Segment& a, const Segment& b) {
return sgn(cross(a.t - a.s, b.t - b.s)) == 0;
}
bool is_orthogonal(const Segment& a, const Segment& b) {
return sgn(dot(a.t - a.s, b.t - b.s)) == 0;
}
int common_tangent_num(const Circle&, const Circle&);
bool has_intersected(const Segment& a, const Point& b) {
return ccw(a.s, a.t, b) == 0;
}
bool has_intersected(const Segment& a, const Segment& b) {
return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) <= 0 &&
ccw(b.s, b.t, a.s) * ccw(b.s, b.t, a.t) <= 0;
}
bool has_intersected(const Line& a, const Point& b) {
const int c = ccw(a.s, a.t, b);
return c != 1 && c != -1;
}
bool has_intersected(const Line& a, const Segment& b) {
return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) != 1;
}
bool has_intersected(const Line& a, const Line& b) {
return sgn(cross(a.t - a.s, b.t - b.s)) != 0 ||
sgn(cross(a.t - a.s, b.s - a.s)) == 0;
}
bool has_intersected(const Circle& a, const Point& b) {
return (a.p - b).norm() == a.r * a.r;
}
bool has_intersected(const Circle& a, const Circle& b) {
const int num = common_tangent_num(a, b);
return 1 <= num && num <= 3;
}
int common_tangent_num(const Circle& a, const Circle& b) {
const Integer dist = (a.p - b.p).norm();
int sign = sgn((a.r + b.r) * (a.r + b.r) - dist);
if (sign == -1) return 4;
if (sign == 0) return 3;
sign = sgn((b.r - a.r) * (b.r - a.r) - dist);
if (sign == -1) return 2;
if (sign == 0) return 1;
return 0;
}
using Polygon = std::vector<Point>;
Integer area(Polygon a) {
const int n = a.size();
a.resize(n + 1);
a.back() = a.front();
Integer res = 0;
for (int i = 0; i < n; ++i) {
res += cross(a[i], a[i + 1]);
}
// return res / 2;
return res;
}
int contains(Polygon a, const Point &b) {
const int n = a.size();
a.resize(n + 1);
a.back() = a.front();
bool is_in = false;
for (int i = 0; i < n; ++i) {
Point p = a[i] - b, q = a[i + 1] - b;
if (sgn(q.y - p.y) == -1) std::swap(p, q);
const int sign = sgn(cross(p, q));
if (sign == 1 && sgn(p.y) != 1 && sgn(q.y) == 1) is_in = !is_in;
if (sign == 0 && sgn(dot(p, q)) != 1) return 1;
}
return is_in ? 2 : 0;
}
bool is_convex(Polygon a) {
const int n = a.size();
a.resize(n + 2);
a[n] = a[0];
a[n + 1] = a[1];
for (int i = 1; i <= n; ++i) {
if (ccw(a[i - 1], a[i], a[i + 1]) == -1) return false;
}
return true;
}
template <bool IS_TIGHT = true>
Polygon monotone_chain(std::vector<Point> ps) {
const int n = ps.size();
std::sort(ps.begin(), ps.end());
Polygon convex_hull(n << 1);
int idx = 0;
for (int i = 0; i < n; convex_hull[idx++] = ps[i++]) {
while (idx >= 2 &&
sgn(cross(convex_hull[idx - 1] - convex_hull[idx - 2],
ps[i] - convex_hull[idx - 1])) < IS_TIGHT) {
--idx;
}
}
for (int i = n - 2, border = idx + 1; i >= 0; convex_hull[idx++] = ps[i--]) {
while (idx >= border &&
sgn(cross(convex_hull[idx - 1] - convex_hull[idx - 2],
ps[i] - convex_hull[idx - 1])) < IS_TIGHT) {
--idx;
}
}
convex_hull.resize(idx - 1);
return convex_hull;
}
std::pair<Point, Point> rotating_calipers(Polygon a) {
const int n = a.size();
if (n <= 2) [[unlikely]] {
assert(n == 2);
return {a[0], a[1]};
}
a.resize(n + 1);
a.back() = a.front();
int high = 0, low = 0;
for (int i = 1; i < n; ++i) {
if (a[i].y > a[high].y) high = i;
if (a[i].y < a[low].y) low = i;
}
Integer max_norm = (a[high] - a[low]).norm();
int i = high, j = low, argmax_i = i, argmax_j = j;
do {
int* i_or_j = &(sgn(cross(a[i + 1] - a[i], a[j + 1] - a[j])) != -1 ? j : i);
if (++(*i_or_j) == n) *i_or_j = 0;
const Integer tmp = (a[j] - a[i]).norm();
if (sgn(tmp - max_norm) == 1) {
max_norm = tmp;
argmax_i = i; argmax_j = j;
}
} while (i != high || j != low);
return {a[argmax_i], a[argmax_j]};
}
} // namespace geometry
bool solve() {
geometry::Segment a, b; cin >> a.s >> b.s >> a.t >> b.t;
return (a.s - a.t).norm() == (b.s - b.t).norm() && !geometry::is_parallel(a, b);
}
int main() {
int t; cin >> t;
while (t--) cout << (solve() ? "Yes\n" : "No\n");
return 0;
}