ZOJ 2967——Colorful Rainbows

题意：有最多5000条线，要求出这些线里面能看到几条。能看到的线是指这条线在一个区间内比其他任何线的y坐标都要大。
思路：根据题目意思，可以看出要求的是在直角坐标系里面最“上面”的那几条线。能看到的线应该组成了一个两边高，中间低的凹的形状。知道了最后要求的大致形状以后，差不多可以想到按从左往右的方式来判断直线是否可见。
先不考虑平行直线，斜率最小的跟斜率最大的直线是一定可见的。从斜率最小的开始考虑。将直线按照斜率从小到大排序。第一条直线即斜率最小的直线，一定是可见的。加入第二条直线，这时因为只有两条直线，所以俩都可见。再加入第三条。第三条的斜率比第二个大，它不可能遮挡住第一条直线，因此它最多只能挡住第二条直线。如果第三条直线与第二条直线的交点的横坐标x1，比第二条直线与第一条直线交点的横坐标x2小或等于，那么第二条直线一定被遮住了（画画图就看出来了）。如果第二条直线没有被遮住，那么这时就可见三条直线。这时，第二条直线有两个交点，将横坐标小的记为p1，将横坐标大的记为p2。
往后每加入一条直线都如此。这样，每一条可见的直线都会记录两个坐标，代表这条直线可见的区间（第一条直线只有与第二条直线一个交点，可以将第一条直线与所有直线中交点最小的给求出来作为它的p1，这样就将第一条直线的处理一般化了）。新加入一条直线以后，如果它会遮挡住直线l，那么在前面判断可见的直线中，斜率比l大的全部都会被遮住。
在判断的过程中，可见的直线相当于一个栈，栈中元素斜率依次增加。每加入一条直线，在里面找不能被挡住的最后一个直线，这条直线以后的所有都看不到了。
我用了两种方法实现，一种是栈顶元素一个一个弹出，另一种是用二分找到最后一个能看到的直线。
代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<map>
#include<cmath>
#include<assert.h>
#include<iomanip>
#include<assert.h>
using namespace std;
typedef long long ll;

int dcmp(double x){
    if(fabs(x)<1e-9)return 0;
    return x<0?-1:1;
}

struct Point{
    double x,y;
    Point(double _x=0,double _y=0):x(_x),y(_y){}
    bool operator < (const Point &a) const {
        return x<a.x;
    }
    bool operator > (const Point &a) const {
        return x>a.x;
    }
    bool operator <= (const Point &a) const {
        return dcmp(x-a.x)<=0;
    }
    bool operator >= (const Point &a) const {
        return dcmp(x-a.x)>=0;
    }
};

struct Line{
    double a,b;
    Point p1;
    Point p2;
    bool operator < (const Line &l) const{
        if(dcmp(a-l.a)!=0)return a<l.a;
        return b>l.b;
    }
}line[5005];

Point crosspoint(Line l1,Line l2){
    double x = (l2.b-l1.b)/(l1.a-l2.a);
    return Point(x,l1.a*x+l1.b);
}

int main()
{
//    freopen("data.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            scanf("%lf%lf",&line[i].a,&line[i].b);
        }
        sort(line,line+n);
        line[0].p1=crosspoint(line[1],line[0]);
        for(int i=1;i<n;++i){
            Point c = crosspoint(line[0],line[i]);
            line[0].p1=min(line[0].p1,c);
        }
        line[0].p1 = Point(line[0].p1.x-1,(line[0].p1.x-1)*line[0].a+line[0].b);//第一条直线的预处理，给它的p1赋值。横坐标减一是为了防止所有点都与第一条直线相交于一点的情况。
        int last=0;
        for(int i=1;i<n;++i){
            if(dcmp(line[i].a-line[i-1].a)==0){
                continue;
            }
            assert(last>=0);
            line[last].p2 = crosspoint(line[last],line[i]);
            if(line[last].p2<=line[last].p1){
                last--;
            }//最后的可见的直线的p2都没有求，新加入直线的时候先把它求出来。
            ///+++++++++++++++++++++++
//            while(last>=0){
//                Point cp = crosspoint(line[last],line[i]);
//                if(cp<=line[last].p1){
//                    last--;
//                } else {
//                    line[i].p1 = cp;
//                    line[last].p2 = cp;break;
//                }
//            }
//            line[++last]=line[i];
//            continue;
            +++++++++++++++++++++++
            int l=0;
            int r=last;
            while(l<=r){
                int mid = (l+r)>>1;
                Point cp = crosspoint(line[i],line[mid]);
                if(line[mid].p1>line[mid].p2)swap(line[mid].p1,line[mid].p2);
                if(cp>line[mid].p1&&cp<=line[mid].p2){
                    l=r=mid;line[mid].p2=cp;line[i].p1=cp;last = mid;break;
                } else if(cp>line[mid].p2){
                    l=mid+1;
                } else if(cp<=line[mid].p1){
                    r=mid-1;
                } else assert(0);
            }
            line[last+1]=line[i];
            last++;
        }
        printf("%d\n",last+1);
    }
    return 0;
}