Codeforces605C：Freelancer'sDreams——凸包算法解析与题解分析

我们把每个二元组看成是平面上的一个点， 那么两个点的线性组合是两点之间的连线， 即x * (a1, b1) + y * (a1, b1) x + y == 1，

那么n个点的线性组合就是一个凸包， 那么我们求出凸包和(0, 0)到(p, q)直线的交的那个较大值就是最优的组合平均速度。

需要注意的是， 直线和凸包可能没有交点， 需要加入(maxa, 0), (0, maxb)这两个点。

#include bits/stdc++.h
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair LL, LL
#define PLI pair LL, int
#define PII pair int, int
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-);
int dcmp(double x) {
if(fabs(x) eps) return ;
else return x ? - : ;
struct Point {
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
double dist(const Point a, const Point b) {
return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));
typedef Point Vector;
Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}
Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}
Point operator * (Vector A, double p) {return Point(A.x * p, A.y * p);}
Point operator / (Vector A, double p) {return Point(A.x / p, A.y / p);}
bool operator (const Vector A, const Vector B) {return A.x B.x || (A.x == B.x A.y B.y);}
bool operator == (const Vector A, const Point B) {return dcmp(A.x - B.x) == dcmp(A.y - B.y) == ;}
double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;}
double Length(Vector A) {return sqrt(Dot(A, A));}
double Angle(Vector A, Vector B) {return acos(Dot(A, B)/Length(A)/Length(B));}
double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
double Area2(Point A, Point B, Point C) {return Cross(B-A, C-A);}
bool IsPointOnSegment(const Point p, const Point a1, const Point a2) {
if(dcmp(Cross(a1-p,a2-p))) return ;
else if(dcmp(p.x-min(a1.x,a2.x)) = dcmp(p.x-max(a1.x,a2.x)) =
dcmp(p.y-min(a1.y,a2.y)) = dcmp(p.y-max(a1.y,a2.y)) = ) return ;
else return ;
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) {
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
int ConvexHull(vector Point p, vector Point ch) {
int n = p.size(), m = ;
sort(p.begin(), p.end());
for(int i = ; i i++) {
while(m dcmp(Cross(ch[m-]-ch[m-], p[i]-ch[m-])) = ) ch.pop_back(), m--;
ch.push_back(p[i]); m++;
}
int k = m;
for(int i = n - ; i i--) {
while(m k dcmp(Cross(ch[m-]-ch[m-], p[i]-ch[m-])) = ) ch.pop_back(), m--;
ch.push_back(p[i]); m++;
}
return m;
int n, p, q;
vector Point pt, ch;
int main() {
scanf("%d%d%d", n, p,
int mxa = -inf, mxb = -inf;
for(int i = ; i i++) {
int a, b; scanf("%d%d", a,
mxa = max(mxa, a);
mxb = max(mxb, b);
pt.push_back(Point(a, b));
}
pt.push_back(Point(mxa, ));
pt.push_back(Point(, mxb));
int m = ConvexHull(pt, ch);
Point v = Point(p, q);
Point ans = Point(-, -);
for(int i = ; i m - ; i++) {
if(dcmp(Cross(ch[i], v)) * dcmp(Cross(v, ch[i + ])) = ) {
if(Cross(v, ch[i + ] - ch[i]) == ) continue;
Point pp = GetLineIntersection(Point(, ), v, ch[i], ch[i + ] - ch[i]);
if(pp.x ans.x) ans = pp;
}
}
printf("%.12f\n", v.x / ans.x);
return ;
/*
*/