我的第一个半平面交(1007: [HNOI2008]水平可见直线)

点击打开链接

Description

Input

Output

Sample Input

Sample Output

YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
首先处理直线将斜率相同的按B值得大小排序，大的在上，小的在下，只需判断斜率是否相同，如果相同，直接跳过，否则判断交点，stack数组装的是可见直线的id(排序后的)，如果stack的顶部和第二个直线的交点与当前的直线和stack顶部的比横坐标小就装入stack中，否则，stack,弹出栈顶元素；反复操作；

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	double a,b;
	int d;
}line[50008];
int cmp(node x,node y)
{
	if(x.a==y.a)
	return x.b>y.b;
	return x.a<y.a;
}
int stack[50008],stack2[50008];

int main()
{
	int n,i,j,k,m,d;
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{scanf("%lf%lf",&line[i].a,&line[i].b);
	line[i].d=i+1;}
	sort(line,line+m,cmp);
	stack[0]=0;
	i=1;d=1;
	while(i<m)
	{
		if(line[i].a!=line[i-1].a)
		break;
		i++;
	}
	stack[d++]=i;
	for(;i<m;i++)
	{
		if(line[i].a==line[stack[d-1]].a)
		continue;
		double aa=line[i].a,bb=line[i].b;
		while(1)
		{
			if(d==1)
			{stack[d++]=i;
			break;}
			double cc=line[stack[d-1]].a,dd=line[stack[d-1]].b;
			double ee=line[stack[d-2]].a,ff=line[stack[d-2]].b;
            double x=(dd-bb)/(aa-cc),y=(ff-bb)/(aa-ee);
			if(x>y)
			{stack[d++]=i;break;}
			else 
			d--;
		}
	}
	for(i=0;i<d;i++)
	stack2[i]=line[stack[i]].d;
	sort(stack2,stack2+d);
	for(i=0;i<d-1;i++) 
	printf("%d ",stack2[i]);
	printf("%d\n",stack2[d-1]);
	return 0;
}