#951662 (C++23) No.2628 Shrinkage

提出ソース

結果

問題	No.2628 Shrinkage
ユーザー	Misuki
提出日時	2024-02-16 23:23:05
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	5,446 bytes
コンパイル時間	2,379 ms
コンパイル使用メモリ	200,624 KB
実行使用メモリ	6,548 KB
最終ジャッジ日時	2024-02-16 23:23:28
合計ジャッジ時間	3,376 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	AC	2 ms 6,548 KB
testcase_05	AC	2 ms 6,548 KB
testcase_06	AC	2 ms 6,548 KB
testcase_07	AC	2 ms 6,548 KB
testcase_08	AC	2 ms 6,548 KB
testcase_09	AC	2 ms 6,548 KB
testcase_10	AC	2 ms 6,548 KB
testcase_11	AC	2 ms 6,548 KB
testcase_12	AC	2 ms 6,548 KB
testcase_13	AC	2 ms 6,548 KB
testcase_14	AC	2 ms 6,548 KB
testcase_15	AC	2 ms 6,548 KB
testcase_16	AC	2 ms 6,548 KB
testcase_17	AC	2 ms 6,548 KB
testcase_18	AC	2 ms 6,548 KB
testcase_19	AC	2 ms 6,548 KB
testcase_20	AC	2 ms 6,548 KB
testcase_21	AC	2 ms 6,548 KB
testcase_22	AC	2 ms 6,548 KB
testcase_23	AC	2 ms 6,548 KB
testcase_24	AC	2 ms 6,548 KB
testcase_25	AC	2 ms 6,548 KB
testcase_26	AC	2 ms 6,548 KB
testcase_27	AC	3 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("O2")
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <compare>
#include <complex>
#include <concepts>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numbers>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <span>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>

#define int ll
#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)
#define INT128_MIN (-INT128_MAX - 1)

#define clock chrono::steady_clock::now().time_since_epoch().count()

#ifdef DEBUG
#define dbg(x) cout << (#x) << " = " << x << '\n'
#else
#define dbg(x)
#endif

namespace R = std::ranges;
namespace V = std::views;

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
//#define double ldb

template<class T>
ostream& operator<<(ostream& os, const pair<T, T> pr) {
  return os << pr.first << ' ' << pr.second;
}
template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &arr) {
  for(const T &X : arr)
    os << X << ' ';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &vec) {
  for(const T &X : vec)
    os << X << ' ';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T> &s) {
  for(const T &x : s)
    os << x << ' ';
  return os;
}

//source: KACTL

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

using P = Point<int>;

//source: KACTL

template<class P>
double lineDist(const P& a, const P& b, const P& p) {
	return (double)(b-a).cross(p-a)/(b-a).dist();
}

P linearTransformation(const P& p0, const P& p1,
		const P& q0, const P& q1, const P& r) {
	P dp = p1-p0, dq = q1-q0, num(dp.cross(dq), dp.dot(dq));
	return q0 + P((r-p0).cross(num), (r-p0).dot(num))/dp.dist2();
}

template<class P> bool onSegment(P s, P e, P p) {
	return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

template<class P>
int sideOf(P s, P e, P p) { return sgn(s.cross(e, p)); }

template<class P>
int sideOf(const P& s, const P& e, const P& p, double eps) {
	auto a = (e-s).cross(p-s);
	double l = (e-s).dist()*eps;
	return (a > l) - (a < -l);
}

template<class P>
bool lineInter(P s1, P e1, P s2, P e2) {
	auto d = (e1 - s1).cross(e2 - s2);
	if (d == 0) // if parallel
    return false;
  else
    return true;
}

template<class P> vector<P> segInter(P a, P b, P c, P d) {
	auto oa = c.cross(d, a), ob = c.cross(d, b),
	     oc = a.cross(b, c), od = a.cross(b, d);
	// Checks if intersection is single non-endpoint point.
	if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
		return {(a * ob - b * oa) / (ob - oa)};
	set<P> s;
	if (onSegment(c, d, a)) s.insert(a);
	if (onSegment(c, d, b)) s.insert(b);
	if (onSegment(a, b, c)) s.insert(c);
	if (onSegment(a, b, d)) s.insert(d);
	return {begin(s), end(s)};
}

template<class P>
P lineProj(P a, P b, P p, bool refl=false) {
	P v = b - a;
	return p - v.perp()*(1+refl)*v.cross(p-a)/v.dist2();
}

template<class P>
bool sameDir(P a, P b, P c, P d) {
  P l = b - a, r = d - c;
  l.x /= max(abs(l.x), 1ll), l.y /= max(abs(l.y), 1ll);
  r.x /= max(abs(r.x), 1ll), r.y /= max(abs(r.y), 1ll);
  return l == r;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(NULL);

  int t; cin >> t;
  while(t--) {
    P a, b, c, d; cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
    if (a == c and b == d) {
      cout << "Yes\n";
      continue;
    }
    if (lineInter(a, b, c, d) or !sameDir(a, b, c, d) or (c - d).dist2() >= (a - b).dist2()) {
      cout << "No\n";
    } else {
      cout << "Yes\n";
    }
  }

  return 0;
}

yukicoder

結果

テストケース

ソースコード