ZOJ - 2967 Colorful Rainbows
题目大意：给你道彩虹，每条彩虹有两个属性，a斜率和b截距，也就是彩虹描述为y=ax+b的直线，并且不存在垂直的彩虹以及一样的彩虹。然后就说明，如果一条彩虹能在取任意x值时的y值大于其他所有彩虹，那么这条彩虹就能被看见，（也就是y轴从上往下不被其他彩虹完全挡住），给定一些彩虹的信息，问能看见几条彩虹？（一开始时理解错题意了~~~）
首先我们是可以知道的，如果斜率a相同，那么截距b小的明显会被大的挡住，所以我们只处理同斜率a中截距b最大的节点，这样剩下的彩虹斜率都不相同，彼此之间都会有交点。那我们可以知道，从两直线相交的交点为中心，相同x值下，比交点x值小的那边斜率小的直线y值大，比交点x值大的那边斜率大的直线y值大。所以我们先将彩虹按斜率排序，然后再维护个和上一条能看见的交点的x值的单调递增栈就可以了。为什么呢？
因为只有两条直线相交时，从上往下，肯定两条直线都能看到，而这时如果加入了第三条直线，（假设直线按斜率大小排序好了），那么假设第一条直线和第二条直线的交点x值为x1,然后第二条直线和第三条直线的交点x值为x2,如果x2>x1的话，那么在x1<x<x2之间第二条直线的y值比第一条和第三条的都大，并不会被挡住。而如果x2<=x1的话，因为x<=x1时，第二条直线已经被第一条直线挡住了，而x>=x2，第二条直线又会被第三条直线挡住，所以这时第二条直线已经完全被挡住了，直接去掉，也就这样一直维护一个单调栈，最后栈的大小就是能看见的彩虹数。（画三条线就可以理解咯~）
1 #include<cstdio> 2 #include<algorithm> 3 #include<stack> 4 using namespace std; 5 const int N=5118; 6 struct Line{ 7 double a,b,x; 8 Line(){} 9 Line(Line &l,double y){ 10 a=l.a,b=l.b,x=y; 11 } 12 }L[N]; 13 int t,n; 14 bool cmp(Line &l1,Line &l2){ 15 return l1.a==l2.a ? l1.b>l2.b : l1.a<l2.a; 16 } 17 int main() 18 { 19 scanf("%d",&t); 20 while(t--) 21 { 22 scanf("%d",&n); 23 for(int i=0;i<n;i++) 24 scanf("%lf%lf",&L[i].a,&L[i].b); 25 sort(L,L+n,cmp); 26 stack<Line> s; 27 s.push(Line(L[0],-0x3f3f3f3f)); 28 for(int i=1;i<n;i++) 29 { 30 if(L[i].a==L[i-1].a) 31 continue; 32 while(!s.empty()) 33 { 34 Line t=s.top(); 35 double x=(t.b-L[i].b)/(L[i].a-t.a); 36 if(t.x<x) 37 { 38 s.push(Line(L[i],x)); 39 break; 40 } 41 else 42 s.pop(); 43 } 44 } 45 printf("%d ",s.size()); 46 } 47 return 0; 48 }