Submission #15302451


Source Code Expand

Copy
// #pragma GCC target ("avx")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define endl '\n'

#pragma region TEMPLATE

/* TYPE */
typedef long long ll;       typedef long double ld;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
typedef vector<pii> vpii;   typedef vector<pll> vpll;
typedef vector<int> vi;     typedef vector<ll> vl;
typedef vector<string> vst; typedef vector<bool> vb;
typedef vector<ld> vld;     typedef vector<vector<int>> vvi;
template<typename T, typename Cmp = less<>> using prique = priority_queue<T, vector<T>, Cmp>;
template<typename T> using prique_r = prique<T, greater<>>;
/* CONSTANT */
#define ln '\n'
const int INF = 1 << 30;    const ll INFF = 1LL << 60;  const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int MOD = 1e9 + 7;    const int MODD = 998244353; const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const double EPS = 1e-9;    const ld PI = 3.14159265358979323846264338327950288;
const int dx[] = { 1, 0, -1,  0,  1, -1, -1, 1, 0 };
const int dy[] = { 0, 1,  0, -1, -1, -1,  1, 1, 0 };
/* CONTAINER */
#define PB              emplace_back
#define ALL(v)          (v).begin(), (v).end()
#define RALL(v)         (v).rbegin(), (v).rend()
#define SORT(v)         sort(ALL(v))
#define RSORT(v)        sort(RALL(v))
#define LESS(x, val)    (lower_bound(x.begin(), x.end(), val) - x.begin())
#define LEQ(x, val)     (upper_bound(x.begin(), x.end(), val) - x.begin())
#define GREATER(x, val) (int)(x).size() - LEQ((x), (val))
#define GEQ(x, val)     (int)(x).size() - LESS((x), (val))
#define UNIQUE(v)       sort(ALL(v)); (v).erase(unique(ALL(v)), (v).end())
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }
template<typename T, typename U, typename... V> enable_if_t<is_same<T, U>::value != 0> fill_v(U &u, const V... v) { u = U(v...); }
template<typename T, typename U, typename... V> enable_if_t<is_same<T, U>::value == 0> fill_v(U &u, const V... v) { for (auto &e : u) fill_v<T>(e, v...); }
/* LOOP */
#define _overload3(_1, _2, _3, name, ...) name
#define _REP(i, n)      REPI(i, 0, n)
#define REPI(i, a, b)   for (ll i = (ll)a; i < (ll)b; ++i)
#define REP(...)        _overload3(__VA_ARGS__, REPI, _REP,)(__VA_ARGS__)
#define _RREP(i, n)     RREPI(i, n, 0)
#define RREPI(i, a, b)  for (ll i = (ll)a; i >= (ll)b; --i)
#define RREP(...)       _overload3(__VA_ARGS__, RREPI, _RREP,)(__VA_ARGS__)
#define EACH(e, v)      for (auto& e : v)
#define PERM(v)         sort(ALL(v)); for (bool c##p = true; c##p; c##p = next_permutation(ALL(v)))
/* INPUT */
template<typename T> void SSS(T& t) { cin >> t; }
template<typename Head, typename... Tail> void SSS(Head&& head, Tail&&... tail) { cin >> head; SSS(tail...); }
#define SS(T, ...)      T __VA_ARGS__; SSS(__VA_ARGS__);
#define SV(T, v, n)     vector<T> v(n); for (auto& i : v) cin >> i;
#define SVV(T, v, n, m) vector<vector<T>> v(n, vector<T>(m)); for (auto& r : v) for (auto& i : r) cin >> i;
/* OUTPUT */
// Yes / No
inline int YES(bool x) { cout << (x ? "YES"  : "NO") << endl; return 0; }
inline int Yes(bool x) { cout << (x ? "Yes"  : "No") << endl; return 0; }
inline int yes(bool x) { cout << (x ? "yes"  : "no") << endl; return 0; }
inline int yES(bool x) { cout << (x ? "yES"  : "nO") << endl; return 0; }
inline int Yay(bool x) { cout << (x ? "Yay!" : ":(") << endl; return 0; }
// PROTOTYPE DECLARATION
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &j);
template<typename... T> ostream &operator<<(ostream &os, const tuple<T...> &t);
template<class C, enable_if_t<!is_same<C, string>::value, decltype(declval<const C &>().begin(), nullptr)> = nullptr> ostream& operator<<(ostream &os, const C &c);
template<typename T> ostream &operator<<(ostream &os, const stack<T> &j);
template<typename T> ostream &operator<<(ostream &os, const queue<T> &j);
template<typename T, typename C, typename Cmp> ostream &operator<<(ostream &os, const priority_queue<T, C, Cmp> &j);
// IMPLEMENTATION
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &j) { return os << '{' << j.first << ", " << j.second << '}'; }
template<size_t num = 0, typename... T> enable_if_t<num == sizeof...(T)> PRINT_TUPLE(ostream &os, const tuple<T...> &t) {}
template<size_t num = 0, typename... T> enable_if_t<num <  sizeof...(T)> PRINT_TUPLE(ostream &os, const tuple<T...> &t) { os << get<num>(t); if (num + 1 < sizeof...(T)) os << ", "; PRINT_TUPLE<num + 1>(os, t); }
template<typename... T> ostream &operator<<(ostream &os, const tuple<T...> &t) { PRINT_TUPLE(os << '{', t); return os << '}'; }
template<class C, enable_if_t<!is_same<C, string>::value, decltype(declval<const C &>().begin(), nullptr)>> ostream& operator<<(ostream &os, const C &c) { os << '{'; for (auto it = begin(c); it != end(c); it++) { if (begin(c) != it) os << ", "; os << *it; } return os << '}'; }
template<typename T> ostream &operator<<(ostream &os, const stack<T> &j) { deque<T> d; for (auto c = j; !c.empty(); c.pop()) d.push_front(c.top());  return os << d; }
template<typename T> ostream &operator<<(ostream &os, const queue<T> &j) { deque<T> d; for (auto c = j; !c.empty(); c.pop()) d.push_back(c.front()); return os << d; }
template<typename T, typename C, typename Cmp> ostream &operator<<(ostream &os, const priority_queue<T, C, Cmp> &j) { deque<T> d; for (auto c = j; !c.empty(); c.pop()) d.push_front(c.top());  return os << d; }
// OUTPUT FUNCTION
template<typename T> int PV(T &v) { int sz = v.size(); for (int i = 0; i < sz; ++i) cout << v[i] << " \n"[i == sz - 1]; return 0; }
inline int print() { cout << endl; return 0; }
template<typename Head> int print(Head&& head){ cout << head; return print(); }
template<typename Head, typename... Tail> int print(Head&& head, Tail&&... tail) { cout << head << " "; return print(forward<Tail>(tail)...); }
#ifdef LOCAL
inline void dump() { cerr << endl; }
template<typename Head> void dump(Head&& head) { cerr << head; dump(); }
template<typename Head, typename... Tail> void dump(Head&& head, Tail&&... tail) { cerr << head << ", "; dump(forward<Tail>(tail)...); }
#define debug(...) do {cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; dump(__VA_ARGS__); } while (false)
#else
#define dump(...)
#define debug(...)
#endif
/* OTHER */
#define fi              first
#define se              second
#define MP              make_pair
#define MT              make_tuple
template<typename T, typename A, typename B> inline bool between(T x, A a, B b) { return ((a <= x) && (x < b)); }
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
inline ll POW(ll a, ll b) { ll r = 1; do { if (b & 1)  r *= a; a *= a; } while (b >>= 1); return r; }
struct abracadabra {
    abracadabra() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        cerr << fixed << setprecision(5);
    };
} ABRACADABRA;

#pragma endregion

int solve();

signed main() {

    // int _T; cin >> _T; for (int t = 1; t <= _T; ++t)
    solve();

}

using pdd = pair<ld, ld>;

// AB間の距離
ld dist(pdd A, pdd B) {
    auto [ax, ay] = A;
    auto [bx, by] = B;
    return hypot<ld>(ax - bx, ay - by);
}

// AからB方向にd動かす
pair<ld, ld> mv(pdd A, pdd B, ld d) {
    auto [ax, ay] = A;
    auto [bx, by] = B;
    ld AB = dist(A, B);
    pair<ld, ld> dif(bx - ax, by - ay);
    dif.fi *= d / AB;
    dif.se *= d / AB;
    dif.fi += A.fi;
    dif.se += A.se;
    return dif;
}

ld area(pdd A, pdd B, pdd C) {
    B.fi -= A.fi;
    B.se -= A.se;
    C.fi -= A.fi;
    C.se -= A.se;
    ld ret = B.fi * C.se - B.se * C.fi;
    return abs(ret) / 2.0;
}

// Aから辺BCに引いて三角形を分断する
ld calc(pdd A, pdd B, pdd C) {
    ld AB = dist(A, B);
    ld BC = dist(B, C);
    ld CA = dist(C, A);

    auto f_trn = [&](ld c) -> ld {
        auto P = mv(B, C, c);   // BC上の点
        ld AP = dist(A, P);
        ld BP = dist(B, P);
        ld CP = dist(C, P);
        ld S_ABP = area(A, B, P);
        ld S_ACP = area(A, C, P);
        ld r_ABP = (S_ABP * 2.0) / (AB + BP + AP);
        ld r_ACP = (S_ACP * 2.0) / (CA + AP + CP);
        return min(r_ABP, r_ACP);
    };
    
    // BからCに向けて離していく
    ld l = 0, r = BC;
    for (int _ = 0; _ < 100; ++_) {
        ld c1 = (l * 2 + r) / 3;
        ld c2 = (l + r * 2) / 3;
        if (f_trn(c1) < f_trn(c2)) l = c1;
        else r = c2;
    }

    return f_trn(l);
}

int solve() {

    pii A, B, C;
    cin >> A.fi >> A.se;
    cin >> B.fi >> B.se;
    cin >> C.fi >> C.se;
    
    // ld res = 0.0;
    // chmax(res, calc(A, B, C));
    // chmax(res, calc(B, C, A));
    // chmax(res, calc(C, A, B));
    // print(res);

    ld S = area(A, B, C);
    ld AB = dist(A, B);
    ld BC = dist(B, C);
    ld CA = dist(C, A);
    ld R = (S * 2.0) / (AB + BC + CA);
    auto f = [&](pdd P, pdd Q) -> ld {
        ld d = dist(P, Q);
        return d * R / (2 * R + d);
    };

    // O(1)算数...
    ld res = 0.0;
    chmax(res, f(A, B));
    chmax(res, f(B, C));
    chmax(res, f(C, A));
    print(res);

    return 0;

}

Submission Info

Submission Time
Task B - Inscribed Bicycle
User morio__
Language C++ (GCC 9.2.1)
Score 500
Code Size 9650 Byte
Status
Exec Time 10 ms
Memory 3876 KB

Compile Error

./Main.cpp:10: warning: ignoring #pragma region TEMPLATE [-Wunknown-pragmas]
   10 | #pragma region TEMPLATE
      | 
./Main.cpp:115: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
  115 | #pragma endregion
      | 

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 500 / 500 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 10 ms 3800 KB
001.txt 3 ms 3840 KB
002.txt 3 ms 3876 KB
003.txt 2 ms 3804 KB
004.txt 2 ms 3720 KB
005.txt 2 ms 3724 KB
006.txt 2 ms 3720 KB
007.txt 7 ms 3772 KB
008.txt 3 ms 3752 KB
009.txt 3 ms 3804 KB
010.txt 4 ms 3740 KB
011.txt 4 ms 3740 KB
012.txt 2 ms 3876 KB
013.txt 2 ms 3792 KB
014.txt 2 ms 3804 KB
015.txt 3 ms 3872 KB
example0.txt 2 ms 3844 KB
example1.txt 2 ms 3776 KB