ZOJ 2967-C - Colorful Rainbows

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14130

题意：给出n条y=ai*x+bi的直线。对于这些直线，如果存在x使得该直线y大于其他任意一直线，那么这条直线可以被看见，问有多少条直线可以被看见。

思路：同斜率，肯定是b最大的才能被看到;

先对斜率排序，同效率的只取最大的一个 

第一条线一定可以选放进stack，然后接下来按照这个方法更新：

将当前被判断的线与栈顶的线求交点X，如果X小于等于上一个交点(栈顶与倒数第二个元素的交点),则可以把 栈顶pop出(因为栈顶会被当前的线遮住)  

直到X大于last_x,则把当前线进栈 

因为至少有一条线是可以的，所以对于第一条线，我们可以认为他的last_x是无穷小..... 

把所有的线都判断完 ,stack里存的就是可以被看先的线,size就是答案

参考code：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <set>
#include <vector>
using namespace std;
const int inf =- 2147483640;
int n;
const double eps = 0.00000001;

struct node
{
	double x,y;
	double left;
	node (){}
	node(double a,double b)
	{
		x=a;y=b;
	}
};
int cmp(node a,node b)
{
	if (a.x==b.x)
	return	a.y<b.y;
	else
		return a.x<b.x;
} 

node tm[5005],ans[5005];
stack<node>sb;
int main()
{
//	printf("%.10lf",eps);
	int i,j;
	int t;cin>>t;
	while(t--)
	{
		while(!sb.empty())
			sb.pop();
		scanf("\n%d",&n);
		double a,b;
		for (i=1;i<=n;i++)
		{
			scanf("%lf %lf",&a,&b);
			tm[i].x=a;
			tm[i].y=b;
		}
		sort(tm+1,tm+1+n,cmp);
		int ok=0;
		for (i=1;i<n;i++)
		{
			if (tm[i].x==tm[i+1].x)
				continue;
			ans[++ok]=tm[i];    //去重
		} 
			ans[++ok]=tm[n];		//注意不要漏掉
	 
		ans[1].left=inf;
		sb.push(ans[1]);
		int cun=2;
		int line=1;
		while(!sb.empty() )
		{ 
			if (cun>ok) break;
			node p=ans[cun];		//写成tm数组了。一直wa...

			node hd=sb.top(); 
			double xx=(p.y-hd.y)/(hd.x-p.x);  //交点
	 
			if (hd.left+eps>=xx )
			{
				sb.pop();continue;
			}
			else
			{
				p.left=xx;   //p点与栈中前一个点的交点
				sb.push(p);
				cun++;	

			}
		} 
		printf("%d\n",sb.size());
 
	 
	}
	
	
	return 0;
	
}