Colorful Rainbows ZOJ - 2967 （栈的应用）

超、凢脫俗 2022-05-27 12:57 112阅读 0赞

思路：先排序，斜率从小到大， 斜率相同， b从小到大。斜率相同时， b大的肯定遮挡b小的。所以将斜率相同b小的去掉。

剩下斜率都不同。当直线数量<=2时候， 肯定不会遮挡， 所以当出现第三条直线时，判断它与第二条直线的交点是否在第一条直线与第二条直线交点的右边，是的话不遮挡， 否则会遮挡。若遮挡一直找到第一个不遮挡的为止。

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    using namespace std;
    const double ep=1e-10;
    const int maxn=5e3+10;
    const int INF=0x3f3f3f3f;
    int n, m;
    
    struct node {
    	double k, b;
    } line[maxn];
    
    bool cmp(const node& a1, const node& a2){
    	return a1.k<a2.k || (a1.k==a2.k && a1.b>a2.b);
    }
    
    double GetIntersection(node l1, node l2){
    	return (l2.b-l1.b)/(l1.k-l2.k);
    }
    
    int dcmp(double x){
    	if(fabs(x)<ep)
    		return 0;
    	else return x<0?-1:1;
    }
    
    int main() {
    	int T;
    	scanf("%d", &T);
    	while(T--) {
    		int n;
    		scanf("%d", &n);
    		stack<node> s;
    		for(int i=1; i<=n; i++)
    		{
    			scanf("%lf%lf", &line[i].k, &line[i].b);
    		}
    		
    		sort(line+1, line+1+n, cmp);
    		s.push(line[1]);
    		double pre=line[1].k;
    		for(int i=2; i<=n; i++)
    		{
    			if(dcmp(line[i].k-pre)==0) continue;
    			while(s.size()!=1){
    				node l1, l2;
    				l1=s.top(); s.pop();
    				l2=s.top();
    				
    				double x1, x2;
    				x1=GetIntersection(line[i], l1);
    				x2=GetIntersection(l1, l2);
    				
    				if(dcmp(x1-x2)>0)
    				{
    					s.push(l1); break;
    				}
    			}
    			s.push(line[i]);
    			pre=line[i].k;
    		}
    		printf("%d\n", s.size());
    	}
    
    	return 0;
    }