首页 > 代码库 > ZOJ 3967 Colorful Rainbows --栈的应用

ZOJ 3967 Colorful Rainbows --栈的应用

2024-07-12 15:47:29   213人阅读

题意：给出n条y=ai*x+bi的直线。对于这些直线，如果存在x使得该直线y大于其他任意一直线，那么这条直线可以被看见，问有多少条直线可以被看见。

做法什么的不讲了，参见：http://blog.csdn.net/ten_three/article/details/12289427  以及  http://blog.sina.com.cn/s/blog_7eee8bf3010136d8.html

利用了堆栈来做，总体复杂度O(nlogn)

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>using namespace std;#define N 5006struct node{    double x,y;}p[N],line[N];node stk[N];int cmp(node ka,node kb){    if(ka.x == kb.x)        return ka.y < kb.y;    return ka.x < kb.x;}double calc(node ka,node kb){    double res = (ka.y-kb.y)*1.0/(kb.x-ka.x);    return res;}int main(){    int t,m,n,k;    double now,pre;    int i,j;    int tail;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(i=0;i<n;i++)            scanf("%lf%lf",&p[i].x,&p[i].y);        sort(p,p+n,cmp);        k = 0;        for(i=0;i<n-1;i++)        {            if(p[i].x != p[i+1].x)                line[k++] = p[i];        }        line[k++] = p[n-1];        if(k < 2)        {            printf("%d\n",k);            continue;        }        tail = 0;        stk[tail++] = line[0];        stk[tail++] = line[1];        pre = calc(stk[1],stk[0]);        int ans = 2;        for(i=2;i<k;i++)        {            now = calc(line[i],stk[tail-1]);            while(now <= pre)            {                tail--;                if(tail >= 2)                {                    pre = calc(stk[tail-1],stk[tail-2]);                    now = calc(line[i],stk[tail-1]);                }                else                {                    now = calc(line[i],stk[tail-1]);                    break;                }            }            stk[tail++] = line[i];            pre = now;        }        printf("%d\n",tail);    }    return 0;}
View Code


联系
我们