记录编号	167729	评测结果	AAAAAAAAAAAA
题目名称	[USACO Jan07]考试	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2015-06-28 10:30:37	内存使用	2.98 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEN=50010;
class Point{
public:
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;
		y=_y;
	}
};
void print(const Point &p){
	cout<<"("<<p.x<<" "<<p.y<<")";
}
Point operator + (const Point &a,const Point &b){
	return Point(a.x+b.x,a.y+b.y);
}
Point operator - (const Point &a,const Point &b){
	return Point(a.x-b.x,a.y-b.y);
}
double cross(const Point &a,const Point &b){
	return a.x*b.y-b.x*a.y;
}
double dir_area(const Point &o,const Point &a,const Point &b){//以O为视点看a,b
	return cross(a-o,b-o);
}
bool cmp_angle(const Point &a,const Point &b){
	return dir_area(Point(0,0),a,b)>0;
}
double calc(const Point &a,double m){
	return a.y-m*a.x;
}
int N;
Point P[SIZEN];
double ratio[SIZEN];
double best_out[SIZEN],worst_in[SIZEN];
Point H[SIZEN];
void work(void){
	sort(P+1,P+1+N,cmp_angle);
	Point now(0,0);
	for(int i=N;i>=1;i--){
		now=now+P[i];
		ratio[i]=now.y/now.x;
	}
	int tot=0;
	for(int i=1;i<N;i++){
		while(tot>=1&&H[tot-1].x>=P[i].x) tot--;//滤掉右边的
		while(tot>=2&&dir_area(H[tot-2],H[tot-1],P[i])>=0) tot--;//滤掉不在上凸线上的
		H[tot++]=P[i];//上凸线新加点
		while(tot>=2&&calc(H[tot-1],ratio[i+1])<=calc(H[tot-2],ratio[i+1])) tot--;//滤掉不被当前斜率卡住的
		best_out[i]=calc(H[tot-1],ratio[i+1]);
	}
	tot=0;
	for(int i=N;i>=1;i--){
		while(tot>=1&&H[tot-1].x<=P[i].x) tot--;//滤掉左边的
		while(tot>=2&&dir_area(H[tot-2],P[i],H[tot-1])<=0) tot--;//滤掉不在下凸线上的
		H[tot++]=P[i];//下凸线新加点
		while(tot>=2&&calc(H[tot-1],ratio[i])>=calc(H[tot-2],ratio[i])) tot--;//滤掉不被当前斜率卡住的
		worst_in[i]=calc(H[tot-1],ratio[i]);
	}
	vector<int> ans;
	for(int i=1;i<N;i++) if(worst_in[i+1]<best_out[i]) ans.push_back(i);
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lf%lf",&P[i].y,&P[i].x);
}
int main(){
	freopen("schul.in","r",stdin);
	freopen("schul.out","w",stdout);
	read();
	work();
	return 0;
}