結果
| 問題 | No.2628 Shrinkage |
| ユーザー |
 Today03
|
| 提出日時 | 2024-02-16 21:35:47 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,610 bytes |
| コンパイル時間 | 2,201 ms |
| コンパイル使用メモリ | 209,536 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-09-28 19:50:02 |
| 合計ジャッジ時間 | 2,986 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| 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>
#ifdef LOCAL
#include "./debug.cpp"
#else
#define debug(...)
#define print_line
#endif
using namespace std;
using ll = long long;
#line 2 "geometry/line.hpp"
#line 2 "geometry/geometry-base.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
using namespace std;
using Real = long double;
constexpr Real EPS = 1e-10;
constexpr Real pi = 3.141592653589793238462643383279L;
bool equals(Real a, Real b) { return fabs(b - a) < EPS; }
int sign(Real a) { return equals(a, 0) ? 0 : a > 0 ? 1 : -1; }
template <typename R>
struct PointBase {
using P = PointBase;
R x, y;
PointBase() : x(0), y(0) {}
PointBase(R _x, R _y) : x(_x), y(_y) {}
template <typename T, typename U>
PointBase(const pair<T, U> &p) : x(p.first), y(p.second) {}
P operator+(const P &r) const { return {x + r.x, y + r.y}; }
P operator-(const P &r) const { return {x - r.x, y - r.y}; }
P operator*(R r) const { return {x * r, y * r}; }
P operator/(R r) const { return {x / r, y / r}; }
P &operator+=(const P &r) { return (*this) = (*this) + r; }
P &operator-=(const P &r) { return (*this) = (*this) - r; }
P &operator*=(R r) { return (*this) = (*this) * r; }
P &operator/=(R r) { return (*this) = (*this) / r; }
bool operator<(const P &r) const { return x != r.x ? x < r.x : y < r.y; }
bool operator==(const P &r) const { return x == r.x and y == r.y; }
bool operator!=(const P &r) const { return !((*this) == r); }
P rotate(R rad) const {
return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)};
}
R real() const { return x; }
R imag() const { return y; }
friend R real(const P &p) { return p.x; }
friend R imag(const P &p) { return p.y; }
friend R dot(const P &l, const P &r) { return l.x * r.x + l.y * r.y; }
friend R cross(const P &l, const P &r) { return l.x * r.y - l.y * r.x; }
friend R abs(const P &p) { return sqrt(p.x * p.x + p.y * p.y); }
friend R norm(const P &p) { return p.x * p.x + p.y * p.y; }
friend R arg(const P &p) { return atan2(p.y, p.x); }
friend istream &operator>>(istream &is, P &p) {
R a, b;
is >> a >> b;
p = P{a, b};
return is;
}
friend ostream &operator<<(ostream &os, const P &p) {
return os << p.x << " " << p.y;
}
};
using Point = PointBase<Real>;
using Points = vector<Point>;
// ccw, 点の進行方向
int ccw(const Point &a, const Point &b, const Point &c) {
Point x = b - a, y = c - a;
if (cross(x, y) > EPS) return +1; // 反時計回り
if (cross(x, y) < -EPS) return -1; // 時計回り
if (min(norm(x), norm(y)) < EPS * EPS) return 0; // c=a または c=b
if (dot(x, y) < EPS) return +2; // c-a-b の順で一直線
if (norm(x) < norm(y)) return -2; // a-b-c の順で一直線
return 0; // a-c-b の順で一直線
}
#line 2 "geometry/polygon.hpp"
#line 4 "geometry/polygon.hpp"
using Polygon = vector<Point>;
// 多角形の内部に点があるか？
// OUT : 0, ON : 1, IN : 2
int contains_polygon(const Polygon &Q, const Point &p) {
bool in = false;
for (int i = 0; i < (int)Q.size(); i++) {
Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;
if (imag(a) > imag(b)) swap(a, b);
if (sign(imag(a)) <= 0 && 0 < sign(imag(b)) && sign(cross(a, b)) < 0)
in = !in;
if (equals(cross(a, b), 0) && sign(dot(a, b)) <= 0) return 1;
}
return in ? 2 : 0;
}
// 多角形の面積
Real area(const Polygon &p) {
Real A = 0;
for (int i = 0; i < (int)p.size(); ++i) {
A += cross(p[i], p[(i + 1) % p.size()]);
}
return A * 0.5;
}
// 頂点集合から凸包を生成
// boundary : 周上の点も列挙する場合 true
template <bool boundary = false>
Polygon convex_hull(vector<Point> ps) {
int n = (int)ps.size(), k = 0;
if (n <= 2) return ps;
sort(ps.begin(), ps.end());
vector<Point> ch(2 * n);
// 反時計周り
Real th = boundary ? -EPS : +EPS;
for (int i = 0; i < n; ch[k++] = ps[i++]) {
while (k >= 2 && cross(ch[k - 1] - ch[k - 2], ps[i] - ch[k - 1]) < th) --k;
}
for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) {
while (k >= t && cross(ch[k - 1] - ch[k - 2], ps[i] - ch[k - 1]) < th) --k;
}
ch.resize(k - 1);
return ch;
}
// 凸包の内部に点があるか？
// OUT : 0, ON : 1, IN : 2
int contains_convex(const Polygon &C, const Point &p) {
int N = C.size();
auto b1 = cross(C[1] - C[0], p - C[0]);
auto b2 = cross(C[N - 1] - C[0], p - C[0]);
if (b1 < -EPS or b2 > EPS) return 0;
int L = 1, R = N - 1;
while (L + 1 < R) {
int M = (L + R) / 2;
(cross(p - C[0], C[M] - C[0]) >= 0 ? R : L) = M;
}
auto v = cross(C[L] - p, C[R] - p);
if (equals(v, 0)) {
return 1;
} else if (v > 0) {
return equals(b1, 0) or equals(b2, 0) ? 1 : 2;
} else {
return 0;
}
}
// 凸包が与えられるので最遠点対を返す
// 返り値：頂点番号のペア
pair<int, int> convex_polygon_diameter(const Polygon &p) {
int N = (int)p.size();
int is = 0, js = 0;
for (int i = 1; i < N; i++) {
if (imag(p[i]) > imag(p[is])) is = i;
if (imag(p[i]) < imag(p[js])) js = i;
}
Real maxdis = norm(p[is] - p[js]);
int maxi, maxj, i, j;
i = maxi = is;
j = maxj = js;
do {
if (cross(p[(i + 1) % N] - p[i], p[(j + 1) % N] - p[j]) >= 0) {
j = (j + 1) % N;
} else {
i = (i + 1) % N;
}
if (norm(p[i] - p[j]) > maxdis) {
maxdis = norm(p[i] - p[j]);
maxi = i;
maxj = j;
}
} while (i != is || j != js);
return minmax(maxi, maxj);
}
#line 5 "geometry/line.hpp"
struct Line {
Point a, b;
Line() = default;
Line(const Point &_a, const Point &_b) : a(_a), b(_b) {}
// Ax+By=C
Line(const Real &A, const Real &B, const Real &C) {
if (equals(A, 0)) {
assert(!equals(B, 0));
a = Point(0, C / B);
b = Point(1, C / B);
} else if (equals(B, 0)) {
a = Point(C / A, 0);
b = Point(C / A, 1);
} else if (equals(C, 0)) {
a = Point(0, C / B);
b = Point(1, (C - A) / B);
} else {
a = Point(0, C / B);
b = Point(C / A, 0);
}
}
friend ostream &operator<<(ostream &os, const Line &l) {
return os << l.a << " to " << l.b;
}
friend istream &operator>>(istream &is, Line &l) { return is >> l.a >> l.b; }
};
using Lines = vector<Line>;
bool is_parallel(const Line &a, const Line &b) {
return equals(cross(a.b - a.a, b.b - b.a), 0);
}
bool is_orthogonal(const Line &a, const Line &b) {
return equals(dot(a.a - a.b, b.a - b.b), 0);
}
Point cross_point_ll(const Line &l, const Line &m) {
Real A = cross(l.b - l.a, m.b - m.a);
Real B = cross(l.b - l.a, l.b - m.a);
if (equals(abs(A), 0) && equals(abs(B), 0)) return m.a;
return m.a + (m.b - m.a) * B / A;
}
bool is_intersect_ll(const Line &l, const Line &m) {
Real A = cross(l.b - l.a, m.b - m.a);
Real B = cross(l.b - l.a, l.b - m.a);
if (equals(abs(A), 0) && equals(abs(B), 0)) return true;
return !is_parallel(l, m);
}
// 直線に頂点から垂線を下ろした時の交点
Point projection(const Line &l, const Point &p) {
Real t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
// 凸包を直線で切った時の片方 (直線 a->b の進行方向左側) を返す
Polygon convex_polygon_cut(const Polygon &U, const Line &l) {
Polygon ret;
for (int i = 0; i < (int)U.size(); i++) {
const Point &now = U[i];
const Point &nxt = U[(i + 1) % U.size()];
auto cf = cross(l.a - now, l.b - now);
auto cs = cross(l.a - nxt, l.b - nxt);
if (sign(cf) >= 0) {
ret.emplace_back(now);
}
if (sign(cf) * sign(cs) < 0) {
ret.emplace_back(cross_point_ll(Line(now, nxt), l));
}
}
return ret;
}
int main() {
int T;
cin >> T;
while (T--) {
vector<Point> P(4);
for (int i = 0; i < 4; i++) cin >> P[i].x >> P[i].y;
Line la(P[0], P[2]), lb(P[1], P[3]);
Point crs = cross_point_ll(la, lb);
Real d1 = abs(P[0] - P[2]), d2 = abs(P[1] - P[3]);
Real d3 = abs(P[0] - crs), d4 = abs(P[2] - crs);
puts(abs(d1 / d3 - d2 / d4) < EPS ? "Yes" : "No");
}
}