ztx's Blog

/****************************************\
* Author : ztx
* Title  : [FJOI2007]轮状病毒
* ALG    : dp
* CMT    : 打表,怎么推出来的自行百度 = =
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [FJOI2007]轮状病毒
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#include <iostream>

using namespace std ;

string ans[102] = {
"= =",
"1",
"5",
"16",
"45",
"121",
"320",
"841",
"2205",
"5776",
"15125",
"39601",
"103680",
"271441",
"710645",
"1860496",
"4870845",
"12752041",
"33385280",
"87403801",
"228826125",
"599074576",
"1568397605",
"4106118241",
"10749957120",
"28143753121",
"73681302245",
"192900153616",
"505019158605",
"1322157322201",
"3461452808000",
"9062201101801",
"23725150497405",
"62113250390416",
"162614600673845",
"425730551631121",
"1114577054219520",
"2918000611027441",
"7639424778862805",
"20000273725560976",
"52361396397820125",
"137083915467899401",
"358890350005878080",
"939587134549734841",
"2459871053643326445",
"6440026026380244496",
"16860207025497407045",
"44140595050111976641",
"115561578124838522880",
"302544139324403592001",
"792070839848372253125",
"2073668380220713167376",
"5428934300813767249005",
"14213134522220588579641",
"37210469265847998489920",
"97418273275323406890121",
"255044350560122222180445",
"667714778405043259651216",
"1748099984655007556773205",
"4576585175559979410668401",
"11981655542024930675232000",
"31368381450514812615027601",
"82123488809519507169850805",
"215002084978043708894524816",
"562882766124611619513723645",
"1473646213395791149646646121",
"3858055874062761829426214720",
"10100521408792494338631998041",
"26443508352314721186469779405",
"69230003648151669220777340176",
"181246502592140286475862241125",
"474509504128269190206809383201",
"1242282009792667284144565908480",
"3252336525249732662226888342241",
"8514727565956530702536099118245",
"22291846172619859445381409012496",
"58360810951903047633608127919245",
"152790586683089283455442974745241",
"400010949097364802732720796316480",
"1047242260609005124742719414204201",
"2741715832729650571495437446296125",
"7177905237579946589743592924684176",
"18791999880010189197735341327756405",
"49198094402450621003462431058585041",
"128802283327341673812651951847998720",
"337208755579574400434493424485411121",
"882823983411381527490828321608234645",
"2311263194654570182037991540339292816",
"6050965600552329018623146299409643805",
"15841633607002416873831447357889638601",
"41473935220454921602871195774259272000",
"108580172054362347934782139964888177401",
"284266580942632122201475224120405260205",
"744219570773534018669643532396327603216",
"1948392131377969933807455373068577549445",
"5100956823360375782752722586809405045121",
"13354478338703157414450712387359637585920",
"34962478192749096460599414575269507712641",
"91532956239544131967347531338448885552005",
"239636390525883299441443179440077148943376",
"627376215338105766356982006981782561278125",
"1642492255488433999629502841505270534891001"
} ;

int n ;

int main() {
	#define READ
	#ifdef  READ
		freopen("bzoj_1002.in" ,"r",stdin ) ;
		freopen("bzoj_1002.out","w",stdout) ;
	#endif
//	ios::sync_with_stdio(false) ;
	cin >> n ;
	cout << ans[n] ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}
/*

HP fe[101] ;
HP fo[101] ;
HP ans[101] ;
  	fe[1] = 1 ; fe[2] = 4 ;
	fo[1] = 1 ; fo[2] = 3 ;
	fo[0] = 3;
	fe[0] = 5 ;
	int n = 100 ;
	int m = 55 ;
	for (int i = 3 ; i <= m ; i ++ ) {
		fe[i] = fe[i-1]*fo[0];
		fe[i] = fe[i]-fe[i-2] ;
		fo[i] = fo[i-1]*fo[0];
		fo[i] = fo[i]-fo[i-2] ;
	}
	int k ;
	for (int i = 1 ; i <= 100 ; i ++ ) {
		if (i&1) {
			k = (i+1)>>1 ;
			ans[i] = fo[k]*fo[k]*fe[0] ;
		}
		else {
			k = (i>>1)+1 ;
			ans[i] = fe[k]*fe[k] ;
		}
	}
	for (int i = 1 ; i <= 100 ; i ++ ) {
		cout<<"\""<<ans[i]<<"\","<<endl;
	}

*/

/****************************************\
* Author : ztx
* Title  : [国家集训队2000]叠放箱子
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [国家集训队2000]叠放箱子
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH ;
inline void read(int& ret) {
    ret = 0 ; while (CH=getchar() , CH<'!') ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

#define  maxn  1010LL
#define  maxw  6010LL

int n , ans = 0 , answ = 0 , wei[maxn] , lim[maxn] ;
int f[maxn][maxw] = {0} ;
int pre[maxn][maxw] = {0} ;

void PrintfPath(int now , int w) {
	if (now>n || w<=0) return ;
	PrintfPath(now+1 , pre[now][w]) ;
	if (pre[now][w] != w) printf("%d\n",now) ;
}

int i , w ;
int main() {
	#define READ
	#ifdef  READ
		freopen("boxes.in" ,"r",stdin ) ;
		freopen("boxes.out","w",stdout) ;
	#endif
	read(n) ;
	for (i = 1 ; i <= n ; i ++ ) {
		read(wei[i]) , read(lim[i]) ;
		f[i][wei[i]] = 1 ;
	}
	for (i = n ; i > 0 ; i -- )
		for (w = 6000 ; w > 0 ; w -- ) {
			f[i][w] = f[i+1][w] ;
			pre[i][w] = w ;
			if (w<=lim[i] && f[i][w+wei[i]]<f[i+1][w]+1) {
				f[i][w+wei[i]] = f[i+1][w]+1 ;
				pre[i][w+wei[i]] = w ;
			}
		}
	for (w = 6000 ; w > 0 ; w -- )
		if (f[1][w] > ans) ans = f[1][w] , answ = w ;
	printf("%d\n", ans );
	PrintfPath(1 , answ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [ZOJ1450]最小圆覆盖
* ALG    : 计算几何
* CMT    : 最小圆覆盖模板题
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [ZOJ1450]最小圆覆盖
* ALG    : 计算几何
* CMT    : 最小圆覆盖模板题
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>
#include <cmath>

#define  maxn  110LL

struct point {
	double x , y ;
} points[maxn] , c ;

int n ;

inline double Distance(const point& a , const point& b) {
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) ;
}

point Circumcenter(point& a , point& b , point& c) {
	point ret ;
	double a1 = b.x-a.x , b1 = b.y-a.y , c1 = (a1*a1+b1*b1)/2 ;
	double a2 = c.x-a.x , b2 = c.y-a.y , c2 = (a2*a2+b2*b2)/2 ;
	double d = a1*b2-a2*b1 ;
	ret.x = a.x+(c1*b2-c2*b1)/d ;
	ret.y = a.y+(a1*c2-a2*c1)/d ;
	return ret ;
}

int i , j , k ;
double r ;
void Solve() {
	std::random_shuffle(points , points+n) ;
	c = points[0] ; r = 0 ;/* 注意c和r的初始化 */
	for (i = 1 ; i < n ; i ++ ) {
		if (Distance(points[i] , c) <= r) continue ;
		c = points[i] ; r = 0 ;
		for (j = 0 ; j < i ; j ++ ) {
			if (Distance(points[j] , c) <= r) continue ;
			c.x = (points[i].x+points[j].x)/2 ;
            c.y = (points[i].y+points[j].y)/2 ;
            r = Distance(points[j] , c) ;
            for (k = 0 ; k < j ; k ++ ) {
                if (Distance(points[k] , c) <= r) continue ;
                c = Circumcenter(points[i] , points[j] , points[k]) ;
                r = Distance(points[i] , c) ;
            }
		}
	}
	printf("%.8lf %.8lf %.8lf\n", c.x , c.y , r) ;
}

int main() {
	#define READ
	#ifdef  READ
		freopen("minimalcircle.in" ,"r",stdin ) ;
		freopen("minimalcircle.out","w",stdout) ;
	#endif
	int i ;
	while (scanf("%d",&n) , n) {
		for (i = 0 ; i < n ; i ++ )
			scanf("%lf%lf", &points[i].x , &points[i].y) ;
		Solve() ;
    }
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [HNOI2011]数矩形
* ALG    : 计算几何
* CMT    : 按直线中点和长度排序,再求最大矩形面积 
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HNOI2011]数矩形
* ALG    : 计算几何
* CMT    : 按直线中点和长度排序,再求最大矩形面积 
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>

#define  maxn  1600LL

typedef long long ll ;

struct point {
	ll x , y ;
	point() {} ;
	point(ll xx , ll yy):x(xx),y(yy){}
	bool operator == (const point& b) const {
		return x==b.x && y==b.y ;
	}
	point operator - (const point& b) const {
		return point(x-b.x , y-b.y) ;
	}
	ll operator * (const point& b) const {
		return x*b.y-y*b.x ;
	}
} points[maxn] ;

struct line {
	ll len ;
	point *p1 , *p2 ;
	point midpoint ;
	bool operator < (const line& b) const {
		if (len == b.len) {
			if (midpoint.x == b.midpoint.x)
				return midpoint.y < b.midpoint.y ;
			return midpoint.x < b.midpoint.x ;
		} else return len < b.len ;
	}
} lines[maxn*maxn>>1] ;

inline ll Distance(const point& p1 , const point& p2) {
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ;
}

ll Abs(ll x) {
	return x < 0 ? -x : x ;
}

int n , tot ;
ll ans ;

int i , j ;
int main() {
	#define READ
	#ifdef  READ
		freopen("crectangle.in" ,"r",stdin ) ;
		freopen("crectangle.out","w",stdout) ;
	#endif
	scanf("%d", &n ) ;
	for (i = 1 ; i <= n ; i ++ ) {
		scanf("%lld%lld", &points[i].x , &points[i].y) ;
		for (j = 1 ; j < i ; j ++ ) {
			lines[++tot].len = Distance(points[i],points[j]) ;
			lines[tot].p1 =& points[i] ;
			lines[tot].p2 =& points[j] ;
			lines[tot].midpoint = point(points[i].x+points[j].x , points[i].y+points[j].y) ;
		}
	}
	std::sort(lines+1 , lines+tot+1) ;
	for (i = 1 ; i <= tot ; i ++ )
		for (j = i-1 ; j && lines[i].len==lines[j].len && lines[i].midpoint==lines[j].midpoint ; j -- )
			ans = std::max(ans , Abs(((*lines[i].p1)-(*lines[j].p1))*((*lines[i].p1)-(*lines[j].p2)))) ;
	printf("%lld\n", ans ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [POI1999] 洞穴探险
* ALG    : 网络流 最大流 ISAP算法
* CMT    :
题意: 给定有向无环图,起点为1,终点为n,问有多少人可以通过这个图
      要求在1处出发时每条边只可以走一个人,在n处聚集时,每条边只可以来一个人
分析: 所有连接 1 或 n 的边容量为 1 , 其它边容量为无穷 , 求最大流
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [POI1999] 洞穴探险
* ALG    : 网络流 最大流 ISAP算法
* CMT    :
题意: 给定有向无环图,起点为1,终点为n,问有多少人可以通过这个图
      要求在1处出发时每条边只可以走一个人,在n处聚集时,每条边只可以来一个人
分析: 所有连接 1 或 n 的边容量为 1 , 其它边容量为无穷 , 求最大流
* Time   :
\****************************************/

#include <cstdio>
#include <cstring>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define  maxn  210LL
#define  maxm  40010LL

struct FST { int to , next , flow ; } e[maxm<<1] ;
int star[maxn] , tote ;
inline void FST_init() { memset(star , 0 , sizeof star) ; tote = 1 ; }
inline void AddEdge(int u , int v , int cap) {
	e[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ;
	e[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}

#define  infi     0x3f3f3f3fLL
#define  min(x,y) ((x)<(y)?(x):(y))
int N , S , T ;
int h[maxn] , vh[maxn] ;

int dfs(int u , int flowu) {
int p , tmp = h[u]+1 , flow = 0 , flowv ;
	if (u == T) return flowu ;
	for (p = star[u] ; p ; p = e[p].next) {
		if (e[p].flow && (h[e[p].to]+1==h[u])) {
			flowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
			flow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
			if (flow==flowu || h[S]==N) return flow ;
		}
	}
	for (p = star[u] ; p ; p = e[p].next)
		if (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
	if (--vh[h[u]] == 0) h[S] = N ;
	else ++ vh[h[u]=tmp+1] ;
	return flow ;
}

int SAP() {
	int ret = 0 ;
	memset(vh , 0 , sizeof vh) ;
	memset(h , 0 , sizeof h) ;
	vh[S] = N ;
	while (h[S] < N) ret += dfs(S , infi) ;
	return ret ;
}

int n ;

int  i , u , v , m ;
inline void BuildGraph() {
	FST_init() ;
	read(m) ;
	for (i = 1 ; i <= m ; i ++ ) {
		read(v) ;
		AddEdge(1 , v , 1) ;
	}
	for (u = 2 ; u < n ; u ++ ) {
		read(m) ;
		for (i = 1 ; i <= m ; i ++ ) {
			read(v) ;
			if (v == n) AddEdge(u , v , 1) ;
			else AddEdge(u , v , infi) ;
		}
	}
	N = n , S = 1 , T = n ;
}

int main() {
	#define READ
	#ifdef  READ
		freopen("gro.in" ,"r",stdin ) ;
		freopen("gro.out","w",stdout) ;
	#endif
	read(n) ;
	BuildGraph() ;
	printf("%d\n", SAP() ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [AHOI2008] 上学路线
* ALG    :
* CMT    :
题意: n 点 m 双向边,边有编号和两个权值 t , c ,其中 t 代表时间
      起点为 1 , 终点为 n
      问
      <1>计算出实际上可可和卡卡上学需要花费的最少时间并输出.
      <2>帮助可可设计一个方案，删除输入信息中的一些公交路线，
         使得删除后从家到学校需要的最少时间变大，而被删除路线的 c 和最小
         输出删掉路线的数目, c 的和,和删除路线的方案.
分析: <1>最短路即可.
	  <2>求出最短路网,在最短路网上做最小割得到 c 和的最小值,
         再检查一遍最短路网中哪些边的残量为0,哪些边就应该被删除.
PS : 本代码是在cogs上提交的 bzoj 只要求输出最短路和 c 和.
* Time   :
\****************************************/

/****************************************\
* Author : hzoi_ztx
* Title  : [AHOI2008] 上学路线
* ALG    :
* CMT    :
题意: n 点 m 双向边,边有编号和两个权值 t , c ,其中 t 代表时间
      起点为 1 , 终点为 n
      问
      <1>计算出实际上可可和卡卡上学需要花费的最少时间并输出.
      <2>帮助可可设计一个方案，删除输入信息中的一些公交路线，
         使得删除后从家到学校需要的最少时间变大，而被删除路线的 c 和最小
         输出删掉路线的数目, c 的和,和删除路线的方案.
分析: <1>最短路即可.
	  <2>求出最短路网,在最短路网上做最小割得到 c 和的最小值,
         再检查一遍最短路网中哪些边的残量为0,哪些边就应该被删除.
PS : 本代码是在cogs上提交的 bzoj 只要求输出最短路和 c 和.
* Time   :
\****************************************/

#include <cstdio>
#include <cstring>
#include <algorithm>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define  maxn  2510LL
#define  maxm  125000LL

struct FST { int to , next , len , flow , id ; } re[maxm<<1] , e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 , rstar[maxn] = {0} , rtote = 1 ;
inline void AddEdge(int u , int v , int cap , int id) {
	e[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ; e[tote].id = id ;
	e[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}
inline void AddREdge(int u , int v , int t , int c , int id) {
	re[++rtote].to = v ; re[rtote].len = t ; re[rtote].flow = c ;
	re[rtote].id = id ; re[rtote].next = rstar[u] ; rstar[u] = rtote ;
	re[++rtote].to = u ; re[rtote].len = t ; re[rtote].flow = c ;
	re[rtote].id = id ; re[rtote].next = rstar[v] ; rstar[v] = rtote ;
}

#define  infi     0x3f3f3f3fLL
#define  min(x,y) ((x)<(y)?(x):(y))
int N , S , T ;
int h[maxn] , vh[maxn] ;

int dfs(int u , int flowu) {
int p , tmp = h[u]+1 , flow = 0 , flowv ;
	if (u == T) return flowu ;
	for (p = star[u] ; p ; p = e[p].next) {
		if (e[p].flow && (h[e[p].to]+1==h[u])) {
			flowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
			flow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
			if (flow==flowu || h[S]==N) return flow ;
		}
	}
	for (p = star[u] ; p ; p = e[p].next)
		if (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
	if (--vh[h[u]] == 0) h[S] = N ;
	else ++ vh[h[u]=tmp+1] ;
	return flow ;
}

int SAP() {
	int ret = 0 ;
	memset(vh , 0 , sizeof vh) ;
	memset(h , 0 , sizeof h) ;
	vh[S] = N ;
	while (h[S] < N) ret += dfs(S , infi) ;
	return ret ;
}

#define  sizeque  777LL

int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; }
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; }
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }
bool exist[maxn] = {0} ;

int dis1[maxn] , disn[maxn] ;

void SPFA(int S , int *dis) {
int u , v , p ;
	clear() ; dis[S] = 0 ; push_back(S) ;
	while (!empty()) {
		u = front() ; pop_front() ; exist[u] = false ;
		for (p = rstar[u] ; p ; p = re[p].next) {
			v = re[p].to ;
			if (dis[v] > dis[u]+re[p].len) {
				dis[v] = dis[u]+re[p].len ;
				if (!exist[v]) {
					exist[v] = true ;
					if (!empty() && dis[v]<dis[front()]) push_front(v) ;
					else push_back(v) ;
				}
			}
		}
	}
}

int ans[maxm] = {0} , ansc ;
int main() {
int i , p , u , v , t , c , m , n ;
	#define READ
	#ifdef  READ
		freopen("routez.in" ,"r",stdin ) ;
		freopen("routez.out","w",stdout) ;
	#endif
	read(n) , read(m) ;
	for (i = 1 ; i <= m ; i ++ ) {
		read(u) , read(v) , read(t) , read(c) ;
		AddREdge(u , v , t , c , i) ;
	}
	memset(dis1 , 0x3f , sizeof dis1) ;
	SPFA(1 , dis1) ;
	memset(disn , 0x3f , sizeof disn) ;
	SPFA(n , disn) ;
	printf("%d\n", dis1[n]) ;
	for (u = 1 ; u <= n ; u ++ ) {
		for (p = rstar[u] ; p ; p = re[p].next) {
			v = re[p].to ;
			if (dis1[u]+re[p].len+disn[v] == dis1[n]) {
				AddEdge(u , v , re[p].flow , re[p].id) ;
			}
		}
	}
	N = n , S = 1 , T = n ;
	ansc = SAP() ;
	for (u = 1 ; u <= n ; u ++ ) {
		for (p = star[u] ; p ; p = e[p].next) {
			if (p&1) continue ;
			if (e[p].flow == 0) ans[++ans[0]] = e[p].id ;
		}
	}
	std::sort(ans+1 , ans+ans[0]+1) ;
	printf("%d %d\n", ans[0] , ansc) ;
	for (i = 1 ; i <= ans[0] ; i ++ ) {
		printf("%d\n", ans[i]) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [HNOI2008]水平可见直线
* ALG    : 计算几何
* CMT    :
* 要维护的是一个下凸线一样的东西。即从左到右的交点（左）右边的直线是斜率越来越大的。
* 所以我们可以按斜率从小到大排序后。用一个栈来这样维护。
* 每次新加一条直线k,设当前栈顶直线为stack[top]=j,栈顶前一条直线为stack[top-1]=i,
* 则若(k,j)的交点在(i,j）交点的左边或重合，则j必是被k与i及之前的直线所完全覆盖的，
* 所以把j pop 出。直到不能再pop为止，再把k加入栈中
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HNOI2008]水平可见直线
* ALG    : 计算几何
* CMT    :
* 要维护的是一个下凸线一样的东西。即从左到右的交点（左）右边的直线是斜率越来越大的。
* 所以我们可以按斜率从小到大排序后。用一个栈来这样维护。
* 每次新加一条直线k,设当前栈顶直线为stack[top]=j,栈顶前一条直线为stack[top-1]=i,
* 则若(k,j)的交点在(i,j）交点的左边或重合，则j必是被k与i及之前的直线所完全覆盖的，
* 所以把j pop 出。直到不能再pop为止，再把k加入栈中
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>

#define  maxn  500010LL

struct LINE { int k , b , id ; } lines[maxn] ;

int n , i , top = 0 , sta[maxn] ;
bool flag[maxn] = {0} ;

bool Cmp(const LINE& a , const LINE& b) {
	if (a.k == b.k) return a.b > b.b ; return a.k < b.k ;
}

double CrossX(LINE a , LINE b) { return (double)(b.b-a.b)/(double)(a.k-b.k) ; }

double x1 , x2 ;
bool Check(LINE a , LINE b , LINE c) {
	x1 = CrossX(a , b) ; x2 = CrossX(b , c) ;
	if (x1 <= x2) return true ;
	else return false ;
}

int main() {
//	#define READ
	#ifdef  READ
		freopen(".in" ,"r",stdin ) ;
		freopen(".out","w",stdout) ;
	#endif
	scanf("%d", &n ) ;
	for (i = 1 ; i <= n ; i ++ )
		scanf("%d%d", &lines[i].k , &lines[i].b ) , lines[i].id = i ;
	std::sort(lines+1 , lines+n+1 , Cmp) ;
	for (i = 1 ; i <= n ; i ++ ) {
		if (lines[i].k == lines[i-1].k) continue ;
		while (top>1 && Check(lines[i],lines[sta[top]],lines[sta[top-1]])) flag[lines[sta[top--]].id] = false ;
		sta[++top] = i ; flag[lines[i].id] = true ;
	}
	for (i = 1 ; i <= n ; i ++ ) if (flag[i]) printf("%d ", i ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}