hdu3881

source: http://acm.hdu.edu.cn/showproblem.php?pid=3881

title  : Pirates of the Caribbean

题目简述： 给出风的方向 以及若干岛屿，风速和船速一定，求船从 那个岛到哪个岛航行时的速度最大。

 

/*
把向量(kx, ky)旋转到和y轴重合(所有的点也做类似的操作)，结果就是求两个点的斜率的 绝对值的最大值！
先求斜率的最大值，可以用斜率优化的 方法O(n)解决；然后把每个点绕y轴对称过来，再求一遍斜率的 最大值。
这里需要的 注意的是把(kx,ky)旋转到和y轴重合 实际 是绕原点逆时针旋转了一个角度，设为a,设向量(kx,ky)和
x轴的正轴的 夹角是 b,则a=pi/2 - b, 并且cos(a) = cos(pi/2 - b) = sin(b) =
ky / sqrt(kx*kx+ky*ky), sin(a) = sin(pi/2 - b) = cos(b) =
kx / sqrt(kx*kx+ky*ky)。 点(x, y)绕原点逆时针旋转了a的角度之后的坐标是
(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)), 这样求变换之后的坐标
就免去了求三角函数，避免了 不必要的 精度损失。
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double typev;
typedef pair<int, int> pii;
const int N = 100005;
const double eps = 1e-8;
const double DINF = 1e40;
const double pi = acos(-1.0);

//输入一个整数
template<typename T>
void getSNum(T& ans){
	char ch;
	int s;
	while(true){
		ch = getchar();
		if((ch >= '0' && ch <= '9') || ch == '-') break;
	}
	if(ch == '-'){
		s = -1;
		ans = 0;
	}else{
		s = 1;
		ans = ch -'0';
	}
	while(true){
		ch = getchar();
		if(!(ch >= '0' && ch <= '9')) break;
		ans = ans*10+ch-'0';
	}
	ans *= s;
}

int sign(double a){
	return a < -eps ? -1 : (a > eps);
}
struct point{
	typev x, y;
	int id;
	void read(){
		scanf("%lf%lf", &x, &y);
	}
	void print(){
		printf("(%lf, %lf)\n", x, y);
	}
	point(typev _x=0, typev _y=0):x(_x), y(_y) {}
}ps[N], que[N];
int n;
point k;
typev xmul(point st, point ed1, point ed2){
	return (ed1.x-st.x)*(ed2.y-st.y) - (ed1.y-st.y)*(ed2.x-st.x) ;
}
bool isLess(pii a, pii b){
	return a.first < b.first || (a.first == b.first && a.second < b.second);
}
//点集的斜率的最大值, 下标从0开始，这里ps里的点是按x的升序排的并把取得斜率的
//最大值的两个点的 下标放在ans里,如果有多组解，取(ans.x, ans.y)的字典序最小
double maxSlope(point *ps, int n, pii& ans){
	int l, r, i, k;
	double s, tmp;
	pii ti;
	l = r = 0;
	que[r++] = ps[0];
	s = -DINF;
	for(i = 1; i < n; i++){
		while(r-l >= 2){
			k = sign(xmul(que[l], que[l+1], ps[i]));
			if(k < 0 || (k == 0 && que[l].id < que[l+1].id)) break;
			l++;
		}
		tmp = (ps[i].y-que[l].y)/(ps[i].x-que[l].x);
		ti.first = que[l].id; ti.second = ps[i].id;
		if(sign(s-tmp) < 0 || (sign(s-tmp) == 0 && isLess(ti, ans))){
			s = tmp;
			ans = ti;
		}
		while(r-l >= 2){
			k = sign(xmul(que[r-2], que[r-1], ps[i]));
			if(k > 0 || (k == 0 && que[r-1].id < ps[i].id)) break;
			r--;
		}
		que[r++] = ps[i];
	}
	return s;
}
bool cmpp(point a, point b){
//	return sign(a.x - b.x) < 0 || (sign(a.x-b.x) == 0 && a.y < b.y);
	return (a.x < b.x) || (sign(a.x-b.x) == 0 && a.y < b.y);
}
//点集的斜率的绝对值的最大值, 下标从0开始，并把取得 斜率的最大值的两个点的 下标放在ans里,如果有多
//组解，取(ans.x, ans.y)的字典序最小
double maxSlopeAbs(point* ps, int n, pii& ans){
	//首先判断是否有点的x值相等
	sort(ps, ps+n, cmpp);
	double s = -DINF;
	int i, j, mi;
	pii ti;
	for(i = 0; i < n; i++){
		for(j = i; j < n && sign(ps[j].x-ps[i].x) == 0; j++) ;
		if(j-i > 1){
			for(mi=ps[i].id, i++; i < j; i++){
				ti.first = mi;
				ti.second = ps[i].id;
				if(s < 0 || (s > 0 && isLess(ti, ans))){
					s = DINF;
					ans = ti;
				}
				if(mi > ps[i].id){
					mi = ps[i].id;
				}
			}
		}
		i = j-1;
	}
	if(s > 0){
		return s;
	}
	s = maxSlope(ps, n, ans);
	double tmp;
	int l, r;
	for(i = 0; i < n; i++){
		ps[i].x = 0 - ps[i].x;
	}
	l = 0; r = n-1;
	while(l < r){
		swap(ps[l++], ps[r--]);
	}
	tmp = maxSlope(ps, n, ti);
	if(sign(tmp-s) > 0 || (sign(tmp-s) == 0 && isLess(ti, ans))){
		s = tmp;
		ans = ti;
	}
	return s;
}
point rotate(point st, double Cos, double Sin){
	return point(st.x*Sin- st.y*Cos, st.x*Cos+st.y*Sin);
}
bool input(){
	if(scanf("%d", &n) == EOF) return false;
	k.read();
	int i, g;
	double Cos, Sin, len;
	len = sqrt(k.x*k.x+k.y*k.y);
	Cos = k.x / len;
	Sin = k.y / len;
	for(i = 0; i < n; i++){
		getSNum(g);
		ps[i].x = g;
		getSNum(g);
		ps[i].y = g;
		//所有点绕着原点逆时针旋转某个角度
		ps[i] = rotate(ps[i], Cos, Sin);
		ps[i].id = i+1;
	}
	return true;
}
void solve(){
	pii ans;
	if(k.x == 0 && k.y == 0){
		ans.first = 1;
		ans.second = 2;
	}else{
		maxSlopeAbs(ps, n, ans);
	}
	printf("%d %d\n", ans.first, ans.second);
}
int main(){
	//freopen("in.txt", "r", stdin);
	while(input()) solve();
	return 0;
}