学步园

传送门：【CodeForces】406D Hill Climbing

题目分析：首先用单调栈维护凸包，以此得到树边并建树，然后就是求LCA了，我懒得写倍增法，于是乎写了树链剖分版的LCA，可以说LCA是树链剖分的副产物，顺便求求LCA是毫无问题的~。

当然最快的还是离线Tarjan。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , n

const int MAXN = 100005 ;
const int MAXE = 200005 ;

struct Edge {
	int v ;
	Edge* next ;
} E[MAXE] , *H[MAXN] , *edge ;

struct Point {
	LL x , y ;
	int idx ;
	Point () {}
	Point ( LL x , LL y ) : x ( x ) , y ( y ) {}
	Point operator - ( const Point& p ) const {
		return Point ( x - p.x , y - p.y ) ;
	}
	void input ( int index ) {
		scanf ( "%I64d%I64d" , &x , &y ) ;
		idx = index ;
	}
} p[MAXN] , S[MAXN] ;

int top[MAXN] ;
int siz[MAXN] ;
int son[MAXN] ;
int pre[MAXN] ;
int dep[MAXN] ;
int point ;
int n , q ;

void clear () {
	edge = E ;
	siz[0] = 0 ;
	point = 0 ;
	clr ( H , 0 ) ;
	clr ( son , 0 ) ;
	clr ( pre , 0 ) ;
	clr ( top , 0 ) ;
}

void addedge ( int u , int v ) {
	edge -> v = v ;
	edge -> next = H[u] ;
	H[u] = edge ++ ;
}

void dfs ( int u ) {
	siz[u] = 1 ;
	son[u] = 0 ;
	travel ( e , H , u ) {
		int v = e -> v ;
		if ( v == pre[u] ) continue ;
		pre[v] = u ;
		dep[v] = dep[u] + 1 ;
		dfs ( v ) ;
		if ( siz[v] > siz[son[u]] ) son[u] = v ;
	}
}

void rewrite ( int u , int top_element ) {
	top[u] = top_element ;
	if ( son[u] ) rewrite ( son[u] , top_element ) ;
	travel ( e , H , u ) {
		int v = e -> v ;
		if ( v != son[u] && v != pre[u] ) rewrite ( v , v ) ;
	}
}

int query ( int x , int y ) {
	while ( top[x] != top[y] ) {
		if ( dep[top[x]] > dep[top[y]] ) x = pre[top[x]] ;
		else y = pre[top[y]] ;
	}
	if ( dep[x] < dep[y] ) return x ;
	else return y ;
}

int cross ( const Point& a , const Point& b ) {
	return a.x * b.y - a.y * b.x > 0 ;
}

void solve () {
	int x , y ;
	clear () ;
	For ( i , 1 , n ) p[i].input ( i ) ;
	rev ( i , n , 1 ) {
		while ( point > 1 && cross ( S[point - 1] - p[i] , S[point - 2] - p[i] ) ) -- point ;
		S[point ++] = p[i] ;
		if ( point > 1 ) {
			addedge ( S[point - 2].idx , S[point - 1].idx ) ;
			//printf ( "%d -> %d\n" , S[point - 2].idx , S[point - 1].idx ) ;
		}
	}
	dfs ( n ) ;
	rewrite ( n , n ) ;
	scanf ( "%d" , &q ) ;
	while ( q -- ) {
		scanf ( "%d%d" , &x , &y ) ;
		printf ( "%d\n" , query ( x , y ) ) ;
	}
}
	
int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}