Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.00 KB | None | 0 0
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define sz(x) ((int)x.size ())
  10. #define all(x) (x).begin(), (x).end()
  11. #define re return
  12. #define mp make_pair
  13. #define sqrt(x) sqrt (abs(x))
  14. #define y0 y3451
  15. #define y1 y4562
  16. #define makeunique(x) sort(all(x)), (x).resize (unique(all(x)) - (x).begin())
  17. #define endl '\n'
  18.  
  19. typedef pair <int, int> ii;
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef double D;
  23. typedef long double ld;
  24. typedef unsigned int uint;
  25. typedef vector <string> vs;
  26. typedef vector <int> vi;
  27. typedef vector <ii> vii;
  28. typedef vector <ll> vll;
  29. typedef vector <vi> vvi;
  30.  
  31. template <class T> T abs (T x) { re x > 0 ? x : -x; }
  32. template <class T> T sqr (T x) { re x * x; }
  33. template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
  34. template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
  35.  
  36. #define filename ""
  37.  
  38. const D pi = acos(-1.);
  39. const int N = 3e5 + 20;
  40. const int inf = 1e9 + 7;
  41.  
  42. int n, m;
  43. double eps = 1e-8;
  44.  
  45. struct seg {
  46. double x0, y0, x1, y1;
  47. double get (double x) {
  48. return (x - x0) * (y1 - y0) / (x1 - x0) + y0;
  49. }
  50. } a[N];
  51.  
  52. struct node {
  53. int id;
  54. ll pr;
  55. node* left, * right;
  56. node (int i) {
  57. left = right = 0;
  58. pr = rand() + (rand() << 15);
  59. id = i;
  60. }
  61. };
  62.  
  63. double dist (double x, double y, int i) {
  64.  
  65. return 0;
  66. }
  67.  
  68. bool intersect (int i, int j, double X) {
  69. double ans = inf;
  70. ans = min (ans, dist(a[i].x0, a[i].y0, j));
  71. ans = min (ans, dist(a[i].x1, a[i].y1, j));
  72. ans = min (ans, dist(a[j].x0, a[j].y0, i));
  73. ans = min (ans, dist(a[j].x0, a[j].y0, i));
  74. return ans < X * X;
  75. }
  76.  
  77. void merg (node* l, node* r, node*& t) {
  78. if (!l || !r) { t = l ? l : r; re; }
  79. if (l->pr > r->pr) {
  80. merg (l->right, r, l->right), t = l;
  81. } else {
  82. merg (l, r->left, r->left), t = r;
  83. }
  84. }
  85.  
  86. void split (node* t, node*& l, node*& r, double key, double x) {
  87. if (!t) re;
  88. auto k = a[t->id].get(x);
  89. if (k > key + eps) {
  90. split (t->left, l, t->left, key, x), r = t;
  91. } else {
  92. split (t->right, t->right, r, key, x), l = t;
  93. }
  94. }
  95.  
  96. node* getr (node* root) {
  97. while (root->right) root = root->right;
  98. re root;
  99. }
  100.  
  101. node* getl (node* root) {
  102. while (root->left) root = root->left;
  103. re root;
  104. }
  105.  
  106. bool check (double X) {
  107. vector<pair<pair<double, int>, int>> ev;
  108. for (int i = 0; i < n; i++) {
  109. if (abs(a[i].x0 - a[i].x1) < eps) ev.pb(mp(mp(a[i].x0 - X * 0.5, 1), i));
  110. else {
  111. double x0 = a[i].x0 - X * 0.5;
  112. double x1 = a[i].x1 + X * 0.5;
  113. ev.pb(mp(mp(x0, 0), i));
  114. ev.pb(mp(mp(x1, 2), i));
  115. }
  116. }
  117. sort(all(ev));
  118. ok = false;
  119. for (auto x : ev) {
  120. //
  121. }
  122. re ok;
  123. }
  124.  
  125. int main() {
  126. ios::sync_with_stdio(0);
  127. cin.tie(0); cout.tie(0);
  128. cin >> n;
  129. for (int i = 0; i < n; i++) cin >> a[i].x0 >> a[i].y0 >> a[i].x1 >> a[i].y1;
  130. double l = 0;
  131. double r = inf;
  132. for (int i = 0; i < 60; i++) {
  133. double c = (l + r) * 0.5;
  134. if (check(c)) r = c;
  135. else l = c;
  136. }
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement