Problem

Mikhail the Freelancer dreams of two things: to become a cool programmer and to buy a flat in Moscow. To become a cool programmer, he needs at least p experience points, and a desired flat in Moscow costs q dollars. Mikhail is determined to follow his dreams and registered at a freelance site.

He has suggestions to work on n distinct projects. Mikhail has already evaluated that the participation in the i-th project will increase his experience by ai per day and bring bi dollars per day. As freelance work implies flexible working hours, Mikhail is free to stop working on one project at any time and start working on another project. Doing so, he receives the respective share of experience and money. Mikhail is only trying to become a cool programmer, so he is able to work only on one project at any moment of time.

Find the real value, equal to the minimum number of days Mikhail needs to make his dream come true.

For example, suppose Mikhail is suggested to work on three projects and a1 = 6, b1 = 2, a2 = 1, b2 = 3, a3 = 2, b3 = 6. Also, p = 20 andq = 20. In order to achieve his aims Mikhail has to work for 2.5 days on both first and third projects. Indeed,a1·2.5 + a2·0 + a3·2.5 = 6·2.5 + 1·0 + 2·2.5 = 20 and b1·2.5 + b2·0 + b3·2.5 = 2·2.5 + 3·0 + 6·2.5 = 20.

Input

The first line of the input contains three integers n, p and q (1 ≤ n ≤ 100 000, 1 ≤ p, q ≤ 1 000 000) — the number of projects and the required number of experience and money.

Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 1 000 000) — the daily increase in experience and daily income for working on the i-th project.

Output

Print a real value — the minimum number of days Mikhail needs to get the required amount of experience and money. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let’s assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Examples

input

1
2
3
4

3 20 20
6 2
1 3
2 6

output

1

5.000000000000000

input

1
2
3
4
5

4 1 1
2 3
3 2
2 3
3 2

output

1

0.400000000000000

Note

First sample corresponds to the example in the problem statement.

Solution

题目大意：一个人想要实现理想，实现理想需要\(p\)点经验和\(q\)点金钱。

现在他有\(n\)件事情要做，每件事情都有\(a_i\)的经验和\(b_i\)的金钱，现在他要实现自己的理想，问他需要做多少件事情？（事情可以做一部分，也就是说可以做事件的次数为一个实数）

和Codeforces 605 C是同一题，刷一赠一系列。

这道题我开始先考虑的线性规划，求出对偶问题来跑单纯型就可以了。但是…

搞不懂哪里有问题啊…骆学长说，单纯型操作只需要个位数就可以了，我就单纯的写了个单纯型…估计是第一次写写炸了…（不能怪萌萌哒骆学长[]~(￣▽￣)~*…）

于是我放弃治疗了，看到题解给出一种凸包做法：

如图所示，我们就是把所有的事件放到坐标系中求个凸包，然后看凸包和\((p,q)\)的交点到原点距离\(dis\)，用\((p,q)\)到原点的距离除以\(dis\)就是答案了。

注意：两个绿色的点是为了更好地构建凸包和统计对答案贡献用的，也就是说在事件中我们加入这两个事件就可以了。

这样做的证明方法蒟蒻想了半天，貌似相当于说对答案有用的事件也就两个，我们可以用这两个的“平均速度”来计算对答案的贡献。如果我们枚举的话是\(O(n^2)\)的，我们\(O(n {log} n)\)求出来凸包就可以做了。

虽然涉及实数运算，类型转换，但是感觉时间并没有高到哪里去。

Code

 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

#include <cstdio>
#include <algorithm>
#include <cmath>
int getint() {
	int r = 0; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar());
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r;
}
typedef long long ll;
const int maxn = 100005;
int n, p, q;
int a[maxn], b[maxn], mxa = 0, mxb = 0;
int tbid[maxn], tot = 0;
ll cj(ll x1, ll y1, ll x2, ll y2) {
	return x1*y2-x2*y1;
}
ll x;
bool canput(int id1, int id2, int id3) {
	x = cj(a[id2] - a[id1], b[id2] - b[id1], a[id3] - a[id1], b[id3] - b[id1]);
	return x > 0;
}
void tbpush(int id) {
	if (tot < 2) {
		tbid[tot++] = id;
		return;
	}
	while (!canput(tbid[tot-2], tbid[tot-1], id)) --tot;
	tbid[tot++] = id;
}
int id[maxn];
double k1, k2;
double qq, pp;
bool cmp(int id1, int id2) {
	if (a[id1] == a[id2]) return b[id1] < b[id2];
	k1 = double(b[id1]) / double(a[id1]);
	k2 = double(b[id2]) / double(a[id2]);
	return k1 < k2;
}
void findtb() {
	tbpush(n+2);
	for (int i = 0; i < n; ++i)
		id[i] = i;
	tbpush(n);
	std::sort(id, id+n, cmp);
	for (int i = 0; i < n; ++i) tbpush(id[i]);
	tbpush(n+1);
}
double A, B, C, K, KK;
bool getcross(double x1, double y1, double x2, double y2, double &x, double &y) {
	if (x1 == x2) {
		x = x1;
		y = K*x1;
		
		return (x != 0 || y != 0) && ((y1 <= y && y <= y2) || (y2 <= y && y <= y1));
	}
	if (y1 == y2) {
		x = KK*y1;
		y = y1;
		return (x != 0 || y != 0) && ((x1 <= x && x <= x2) || (x2 <= x && x <= x1));
	}
	A = -double(1)/(x1-x2);
	B = double(1)/(y1-y2);
	C = -y1/(y1-y2)+x1/(x1-x2);
	x = -C/(A+B*K);
	y = -C/(A*KK+B);
	return (x != 0 || y != 0) && ((x1 <= x && x <= x2) || (x2 <= x && x <= x1));
}
int main () {
	n = getint();
	p = getint();
	q = getint();
	qq = q;
	pp = p;
	for (int i = 0; i < n; ++i) {
		a[i] = getint();
		b[i] = getint();
		if (mxa < a[i]) mxa = a[i];
		if (mxb < b[i]) mxb = b[i];
	}
	a[n] = mxa;
	b[n+1] = mxb;
	a[n+2] = b[n+2] = 0;
	findtb();
	double dis, dx, dy, bigdis = sqrt(qq*qq+pp*pp);
	K = qq / pp;
	KK = pp / qq;
	for (int i = 1; i < tot; ++i)
		if (getcross(a[tbid[i-1]], b[tbid[i-1]], a[tbid[i]], b[tbid[i]], dx, dy)) {
			dis = sqrt(dx * dx + dy * dy);
			printf("%.8lf", bigdis / dis);
			return 0;
		}
}