当前位置: 首页 > 工具软件 > Rainbows! > 使用案例 >

【计算几何】ZOJ 2967 Colorful Rainbows

乐正焕
2023-12-01

以下为摘抄的讲解:

    给定直线,对每条直线,传说解不等式组可以过,直接看是否存在一个点在直线之上。(左端点取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,算是中等的耗时。。。

 类似资料: