fork download
copy 
  1. //#pragma GCC optimize("O3,unroll-loops")
  2. //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define int ll
  8. #define endl '\n'
  9. #define unoset unordered_set
  10. #define unomap unordered_map
  11. #define strstr stringstream
  12. #define SZ(a) (int)a.size()
  13. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  14. #define fi first
  15. #define se second
  16. #define lb lower_bound
  17. #define ub upper_bound
  18. #define all(s) s.begin(), s.end()
  19. #define rall(s) s.rbegin(), s.rend()
  20. #define rev reverse
  21. #define gcd __gcd
  22. #define pushb push_back
  23. #define popb pop_back
  24. #define pushf push_front
  25. #define popf pop_front
  26. #define emp emplace
  27. #define empb emplace_back
  28. #define empf emplace_front
  29. #define lcm(a, b) (a / __gcd(a, b) * b)
  30. #define log_base(x, base) log(x) / log(base)
  31. #define debug cerr<<"No errors!",exit(0);
  32. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  33. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  34. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  35. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  36. #define pqueue priority_queue
  37. #define sqrt sqrtl
  38. #define i128 __int128
  39. #define popcount __builtin_popcountll
  40. #define BIT(x, i) (((x) >> (i)) & 1)
  41. #define MASK(x) ((1LL) << (x))
  42. #define want_digit(x) cout << fixed << setprecision(x);
  43. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  44. #define mapa make_pair
  45. #define ms(a, x) memset(a, x, sizeof(a))
  46.  
  47. typedef long long ll;
  48. typedef unsigned long long ull;
  49. typedef long double ldb;
  50. typedef double db;
  51. typedef string str;
  52. typedef pair<int, int> pii;
  53. typedef pair<ll, ll> pll;
  54.  
  55. const int MOD = 1e9 + 7; // 998244353
  56. const int inf = 1e9;
  57. const ll INF = 1e18; // MASK(63) - 1
  58. const int limN = 1e5 + 5;
  59.  
  60. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  61. inline ll random(const ll &L, const ll &R) {
  62.     return uniform_int_distribution<ll> (L, R) (rng);
  63. }
  64.  
  65. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  66.  
  67.  
  68. ldb dist(int x, int y, int u, int v) {
  69.     return sqrt((x - u) * (x - u) + (y - v) * (y - v));
  70. }
  71.  
  72. int ccw(pii p, pii q, pii r) {
  73.     ll val = (q.fi - p.fi) * (r.se - p.se) - (q.se - p.se) * (r.fi - p.fi);
  74.     if (val < 0) return -1;
  75.     if (val > 0) return 1;
  76.     return 0;
  77. }
  78.  
  79. bool on(pii p, pii q, pii r) {
  80.     return r.fi >= min(p.fi, q.fi) && r.fi <= max(p.fi, q.fi) &&
  81.            r.se >= min(p.se, q.se) && r.se <= max(p.se, q.se);
  82. }
  83.  
  84. bool cut(pii a, pii b, pii m, pii n) {
  85.     int o1 = ccw(a, b, m), o2 = ccw(a, b, n);
  86.     int o3 = ccw(m, n, a), o4 = ccw(m, n, b);
  87.  
  88.     if (o1 != o2 && o3 != o4) return true;
  89.     if (!o1 && on(a, b, m)) return true;
  90.     if (!o2 && on(a, b, n)) return true;
  91.     if (!o3 && on(m, n, a)) return true;
  92.     if (!o4 && on(m, n, b)) return true;
  93.     return false;
  94. }
  95.  
  96. pii a, b, m, n;
  97. void solve() {
  98.     cin >> a.fi >> a.se >> b.fi >> b.se >> m.fi >> m.se >> n.fi >> n.se;
  99.     want_digit(10);
  100.  
  101.     if (cut(a, b, m, n)) {
  102.         cout << min(dist(m.fi, m.se, a.fi, a.se) + dist(a.fi, a.se, n.fi, n.se),
  103.                     dist(m.fi, m.se, b.fi, b.se) + dist(b.fi, b.se, n.fi, n.se)) << endl;
  104.     }
  105.     else cout << dist(m.fi, m.se, n.fi, n.se) << endl;
  106. }
  107.  
  108. signed main() {
  109.     ios::sync_with_stdio(false), cin.tie(nullptr);
  110.     #define name "test"
  111.     if (fopen(name".INP", "r")) {
  112.         freopen(name".INP", "r", stdin);
  113.         freopen(name".OUT", "w", stdout);
  114.     }
  115.     bool testCase = false;
  116.     int numTest = 1;
  117.     // cin >> numTest;
  118.     forw (i, 1, numTest) {
  119.         if (testCase) cout << "Case #" << i << ": ";
  120.         solve();
  121.     }
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000000
https://ideone.com/FUNtUS
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!