记录编号	141483	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]水平可见直线	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2014-12-01 23:23:32	内存使用	1.51 MiB

#include <cctype>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <assert.h>
using namespace std;
inline void getd(int &x){
	char c = getchar(); bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*========================================================*/
const int maxn = 50003;
typedef long long LL;
int N;
struct Line{
	int id;
	int A, B;
}line[maxn], St[maxn];
bool operator < (const Line &a, const Line &b){return b.A > a.A;}
inline void init(){
	getd(N);int i;
	for(i = 1;i <= N;++i)
		getd(line[i].A), getd(line[i].B), line[i].id = i;
	sort(line + 1, line + N + 1);
}
int it = 0;
bool inS[maxn];
inline void work(){
	int i;
	St[it++] = line[1];
	for(i = 2;i <= N;++i){
		if(line[i].A == St[it-1].A){
			if(line[i].B > St[it-1].B)
				St[it-1] = line[i];
			else continue;
		}
		while(it > 1){
			LL a = (LL)(St[it-2].B - St[it-1].B) * (line[i].A - St[it-1].A);
			LL b = (LL)(St[it-1].B - line[i].B) * (St[it-1].A - St[it-2].A);
			if(a >= b)--it;
			else break;
		}
		St[it++] = line[i];
	}
	while(it)inS[St[--it].id] = 1;
	for(i = 1;i <= N;++i)
		if(inS[i]) printf("%d ", i);
}
int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1007.in", "r", stdin);
	freopen("bzoj_1007.out", "w", stdout);
	#endif
	init();
	work();
	
	return 0;
}