SHARE
TWEET

Untitled

a guest Aug 25th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top