Description

Input

Output

Sample Input

Sample Output

HINT

Source

这个题其实和计算几何没太大关系，需要用单调栈维护可以被看见的直线数，需注意有一个性质：若直线i没有被完全覆盖，则直线i与i-1的交点在i与i+1交点的左侧，可以自己用笔画一画来验证，为了防止被坑，先用unique将重复的直线清掉，每次清掉单调栈中被完全覆盖的直线，再放入新的直线，所有直线经过此操作后，再用ans数组记下所有可以被看见的直线的编号，sort排序得到升序的直线编号，就解出答案了

#include <stdio.h>#include <cmath>#include <algorithm>#define MAXN 50050using namespace std;double ESP=0.000000000000001; //正无穷小，判断double数是否相等int n,ans[MAXN],top=1; //ans数组保存按直线编号升序输出的答案,栈顶为top-1struct Line{	int A,B,id; //第id条直线,直线解析式为y=ax+b	bool operator==(const Line &b)const { return A == b.A;}    bool operator<(const Line &b)const { return A == b.A ? ( B > b.B ) : A < b.A ; }	void read(int x) //输入直线	{		id=x;		scanf("%d%d",&A,&B);	}};Line ln[MAXN],stack[MAXN]; //数组ln[]保存直线,数组stack[]保存单调栈double getLineItsX(Line l1,Line l2) //求两直线交点横坐标(由一元方程推得){	return (double)(l2.B-l1.B)/(double)(l1.A-l2.A);}void init(){	int i,j;	scanf("%d",&n);	for(i=1;i<=n;i++)		ln[i].read(i); //读取直线}void work(){	//性质:若直线i有露出部分，则直线i与i-1的交点在i与i+1交点的左侧	int i,j; 	sort(&ln[1],&ln[n+1]);	n=unique(&ln[1],&ln[n+1])-&ln[1]; //现在,n=不重复的直线数	for(i=1;i<=n;i++) //将直线一条一条地放入坐标系中，放入一条，就删掉被覆盖看不见的直线	{		while(top>2&&getLineItsX(stack[top-1],stack[top-2])>getLineItsX(stack[top-1],ln[i])-ESP)			top--; //当直线top-1被直线top和top-2覆盖掉时,直线top出栈		stack[top++]=ln[i]; //所有覆盖的直线都删光以后，加入第i条直线	}	for(i=1;i<top;i++)		ans[i]=stack[i].id;	sort(ans+1,ans+top); //对结果按id号升序排序}void output(){	int i,j;	for(i=1;i<top;i++)		printf("%d ",ans[i]);	printf("\n");}int main(){	init();	work();	output();	return 0;}