【计算几何】ZOJ 2967 Colorful Rainbows

以下为摘抄的讲解：

    给定直线，对每条直线，传说解不等式组可以过，直接看是否存在一个点在直线之上。（左端点取max,右端点取min，如果左>=右，直接break掉）。有点ft...O(n^2) n=5000 rp好的可以过.... 

    我用的方法类似于凸包，先把所有直线按照斜率a由小到大排序，斜率相同取b较大的，扔掉b小的。于是所有直线斜率不同。准备一个栈，栈里面存放上一次能看到的“最上面”的直线以及这条直线能看到的范围x(x值右边的部分可以被看到）。初始时，把斜率最小的直线入栈，并记录x值为-inf。然后对第i条直线，所做的是用第i条直线和栈顶直线求交点x,如果这个x值不大于栈顶的x值，则把栈顶元素弹出，继续求交，否则退出。这种判断操作直到栈为空，或者当前栈顶的x值大于栈顶的x值。然后把第i条直线入栈，继续，看后面的直线。最后栈中的直线数就是能看到的。这种做法类似于凸包的方法，除去排序外，每条直线至多出入栈一次，复杂度O(n)。总复杂度是O(nlogn)。

看了讲解，自己写了代码，A的有点虐心。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int n, line_num;

struct Line
{
    double k, b;
} l[5010];

bool cmp(struct Line u, struct Line v)
{
    return u.k<v.k;
}

void jiaodian(Line aa, Line bb, double& x)
{
    x = (bb.b - aa.b) / (aa.k - bb.k);
}

int isexit(double hh)
{
    for(int i = 0; i < line_num; i ++)
        if(l[i].k == hh)
            return i;
    return -1;
}

void solve()
{
    int cnt = 1,dian = 0, xx[5000] = {0};
    double jd[5010] = {0.0}, temp;
    xx[0] = 0;
    for(int i = 1; i < line_num; i++)
    {
        while(1)
        {
            jiaodian(l[xx[cnt - 1]], l[i], temp);

            if((temp > jd[dian - 1] && dian >= 1) || cnt == 1)
            {
                jd[dian ++] = temp;
                xx[cnt ++] = i;
                break;
            }
            else
            {
                cnt --;
                dian --;
            }
        }
    }
    printf("%d\n", cnt);
}

int main()
{
    int cas;
    double hh, ll;
    scanf("%d", &cas);
    while(cas--)
    {
        line_num = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i ++)
        {
            scanf("%lf%lf", &hh, &ll);
            int tee = isexit(hh);
            if(tee == -1)
            {
                l[line_num].k = hh;
                l[line_num].b = ll;
                line_num++;
            }
            else if(l[tee].b < ll)
            {
                l[tee].b = ll;
            }
        }
        sort(l, l+line_num, cmp);
        solve();
    }
    return 0;
}

最后时间100ms，算是中等的耗时。。。