Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- using namespace std;
- #define fi first
- #define se second
- #define pb push_back
- #define sz(x) ((int)x.size ())
- #define all(x) (x).begin(), (x).end()
- #define re return
- #define mp make_pair
- #define sqrt(x) sqrt (abs(x))
- #define y0 y3451
- #define y1 y4562
- #define makeunique(x) sort(all(x)), (x).resize (unique(all(x)) - (x).begin())
- #define endl '\n'
- typedef pair <int, int> ii;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef double D;
- typedef long double ld;
- typedef unsigned int uint;
- typedef vector <string> vs;
- typedef vector <int> vi;
- typedef vector <ii> vii;
- typedef vector <ll> vll;
- typedef vector <vi> vvi;
- template <class T> T abs (T x) { re x > 0 ? x : -x; }
- template <class T> T sqr (T x) { re x * x; }
- template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
- template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
- #define filename ""
- const D pi = acos(-1.);
- const int N = 3e5 + 20;
- const int inf = 1e9 + 7;
- int n, m;
- double eps = 1e-8;
- struct seg {
- double x0, y0, x1, y1;
- double get (double x) {
- return (x - x0) * (y1 - y0) / (x1 - x0) + y0;
- }
- } a[N];
- struct node {
- int id;
- ll pr;
- node* left, * right;
- node (int i) {
- left = right = 0;
- pr = rand() + (rand() << 15);
- id = i;
- }
- };
- double dist (double x, double y, int i) {
- return 0;
- }
- bool intersect (int i, int j, double X) {
- double ans = inf;
- ans = min (ans, dist(a[i].x0, a[i].y0, j));
- ans = min (ans, dist(a[i].x1, a[i].y1, j));
- ans = min (ans, dist(a[j].x0, a[j].y0, i));
- ans = min (ans, dist(a[j].x0, a[j].y0, i));
- return ans < X * X;
- }
- void merg (node* l, node* r, node*& t) {
- if (!l || !r) { t = l ? l : r; re; }
- if (l->pr > r->pr) {
- merg (l->right, r, l->right), t = l;
- } else {
- merg (l, r->left, r->left), t = r;
- }
- }
- void split (node* t, node*& l, node*& r, double key, double x) {
- if (!t) re;
- auto k = a[t->id].get(x);
- if (k > key + eps) {
- split (t->left, l, t->left, key, x), r = t;
- } else {
- split (t->right, t->right, r, key, x), l = t;
- }
- }
- node* getr (node* root) {
- while (root->right) root = root->right;
- re root;
- }
- node* getl (node* root) {
- while (root->left) root = root->left;
- re root;
- }
- bool check (double X) {
- vector<pair<pair<double, int>, int>> ev;
- for (int i = 0; i < n; i++) {
- if (abs(a[i].x0 - a[i].x1) < eps) ev.pb(mp(mp(a[i].x0 - X * 0.5, 1), i));
- else {
- double x0 = a[i].x0 - X * 0.5;
- double x1 = a[i].x1 + X * 0.5;
- ev.pb(mp(mp(x0, 0), i));
- ev.pb(mp(mp(x1, 2), i));
- }
- }
- sort(all(ev));
- ok = false;
- for (auto x : ev) {
- //
- }
- re ok;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> n;
- for (int i = 0; i < n; i++) cin >> a[i].x0 >> a[i].y0 >> a[i].x1 >> a[i].y1;
- double l = 0;
- double r = inf;
- for (int i = 0; i < 60; i++) {
- double c = (l + r) * 0.5;
- if (check(c)) r = c;
- else l = c;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement