CF1388E Uncle Bogdan and Projections

发表于 | 阅读数

$n$个水平线段，求某个投影的角度，使得投影的线段的最右端$-$最左端最小。（投影线段可以接触，不能相交）

借鉴大佬博客

应为要计算出斜率范围，但是明显可以垂直，这里可以让$x,y$轴交换即可。

显然斜率在$k\notin(\frac{xl_i-xr_j}{y_i-y_j},\frac{xr_i-xl_j}{y_i-y_j})$

大小可以交换。然后这里有个小技巧，将所有不可行区间排序，然后通过类似括号匹配，来确定可行的边界。

找到所有边界$O(n^2)$。

显然一个一个验证过于复杂，考虑最大和最小，显然导致距离无限远。

官方题解提到

若任两个线段的投影都不相交，那么我们就一定能够增加、减小 $k$ 的值。由于投影最靠前的线段和投影最靠后的线段的 $y$ 的不同， $k$ 的改变势必能够使之投影的相对位置接近，从而减小答案。

三分即可。$O(n^2\log n)$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pdi pair<double, int>
#define mk make_pair
const double eps = 1e-9;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

struct Line
{
    double l, r, x;
} p[N];
int n;
double calc(double k)

{

    double mx = -1e18, mi = 1e18;
    for (int i = 1; i <= n; i++)
    {
        mx = max(mx, p[i].r - p[i].x * k);
        mi = min(mi, p[i].l - p[i].x * k);
    }
    return mx - mi;
}
int main()
{

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].l >> p[i].r >> p[i].x;
    }
    vector<pdi> o;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            if (p[i].x != p[j].x)
            {
                double l = (p[i].l - p[j].r) / (p[i].x - p[j].x);
                double r = (p[i].r - p[j].l) / (p[i].x - p[j].x);
                if (l > r)
                    swap(l, r);

                o.push_back(mk(l + eps, -1));
                o.push_back(mk(r - eps, 1));
            }
        }
    sort(o.begin(), o.end());
    vector<double> v;
    int g = 0;
    for (auto i : o)
    {
        if (g == 0)
            v.push_back(i.first);
        else if (g == -1 && i.second == 1)
            v.push_back(i.first);
        g += i.second;
    }
    if (v.empty())
        v.push_back(0);
    int l = 0, r = v.size() - 1;
    while (r - l > 2)
    {
        int m1 = l + (r - l) / 3,
            m2 = r - (r - l) / 3;
        if (calc(v[m2]) < calc(v[m1]))
            l = m1;
        else
            r = m2;
    }
    double ans = 1e18;
    for (int i = l; i <= r; ++i)
        ans = min(ans, calc(v[i]));
    printf("%.8f\n", ans);
}