CF605C Freelancer's Dreams

发表于 | 阅读数

有$n$份工作，完成 $1$ 个单位时间的第 $i$ 项工作会获得 $a_i$
$b_i$两项属性值。 工作的单位时间数可以不是整数 。你需要在尽量短的时间内使$\sum a\geq p,\sum b\geq q$

考虑选择一个工作的时候工作的为$k\times (a_i,b_i)$,相当于$(a_i,b_i)这条直线$

如果此时再加入一个工作，安排时间形成新的效率在$(x,y)\in[(a_i,b_i)-(a_ii,b_ii)]$上显然效率最高就是$(p,q)$与其交点。

如果再加入一个点，一定是越往外相交越好，可以画一画。其实就是维护一个凸包。然后枚举凸包上的险段与其交点。求最小比例。

  • 加入$(0,0)$
  • 考虑如果就做一个工作，需要$(x_{max},0)$与$(0,y_{max})$。才能保证可以有交点。
  • 求出交点保证在线段上！
代码 
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int pos;
struct point
{
    double x, y;
    double v, li;
    point operator-(const point &p) const { return (point){x - p.x, y - p.y}; };
    point operator+(const point &p) const { return (point){x + p.x, y + p.y}; };
    double operator^(const point &p) const { return x * p.y - y * p.x; };
    double operator*(const point &p) const { return x * p.x + y * p.y; };
    point operator*(const double &p) const { return (point){x * p, y * p}; };
    double dis() const { return sqrt(x * x + y * y); }

} p[N];
vector<point> g;
double eare(point p1, point p2, point p3)
{
    point p4 = p2 - p1;
    point p5 = p3 - p1;
    return p4 ^ p5;
}
bool cmp(point p1, point p2)
{
    p1 = p1 - g[pos];
    p2 = p2 - g[pos];
    return ((p1 ^ p2) == 0 ? (p1 * p1) < (p2 * p2) : (p1 ^ p2) > 0);
}
point inter_point(point a1, point a2, point b1, point b2) ///返回直线AB和线段CD的交点
{
    // if (!intersect(A, B, C, D))
    //     return {-INF * 1.0, 0}; ///判断直线AB是否与线段CD相交，不相交必须须特判
    point a = a2 - a1;
    point b = b2 - b1;
    double t = ((b1 ^ b) - (a1 ^ b)) / (a ^ b);

    return (a1 + a * t);
}

point s[N];
int top = 0;
double graham()
{
    if (g.size() == 1)
        return 0;
    for (int i = 1; i < g.size(); i++)
        if (g[i].y < g[0].y || (g[i].y == g[0].y && g[i].x < g[0].x))
            swap(g[0], g[i]);
    pos = 0;
    sort(g.begin() + 1, g.end(), cmp);

    s[++top] = g[0];
    for (int i = 1; i < g.size(); i++)
    {
        while (top > 1 && ((g[i] - s[top]) ^ (s[top] - s[top - 1])) >= 0)
            top--;
        s[++top] = g[i];
    }
    s[top + 1] = g[0];
    // double ans = 0;
    // for (int i = 1; i <= top; i++)
    //     ans += (s[i] - s[i + 1]).dis();
    // return ans;
}
int n, A, B;
double ans = 1e9;
double x_max, y_max;
int main()
{
    scanf("%d%d%d", &n, &A, &B);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        g.push_back(p[i]);
        x_max = max(x_max, p[i].x);
        y_max = max(y_max, p[i].y);
    }
    g.push_back((point){0, 0});
    g.push_back((point){0, y_max});
    g.push_back((point){x_max, 0});
    graham();
    point S = (point){A, B};
    point Y = (point){0, 0};
    for (int i = 1; i <= top; i++)
    {

        if (((s[i + 1] - s[i]) ^ (S - Y)) == 0.0)
            continue;
        point jiao = inter_point(S, Y, s[i + 1], s[i]);
        // cout << s[i].x << " " << s[i].y << " " << s[i + 1].x << " " << s[i + 1].y << endl;
        //cout << jiao.x << " " << jiao.y << endl;
        if (jiao.x != 0 && jiao.x >= min(s[i].x, s[i + 1].x) && jiao.x <= max(s[i].x, s[i + 1].x) && jiao.y >= min(s[i].y, s[i + 1].y) && jiao.y <= max(s[i].y, s[i + 1].y))
            ans = A * 1.0 / jiao.x;
    }
    printf("%.15lf\n", ans);
}