Codeforces 593B Anton and Lines

最新推荐文章于 2024-03-22 00:31:42 发布

月黑风高叶

最新推荐文章于 2024-03-22 00:31:42 发布

阅读量378

点赞数

分类专栏： Codefores 文章标签： ACM codeforces

本文链接：https://blog.csdn.net/csdn364988181/article/details/50531436

版权

Codefores 专栏收录该内容

34 篇文章

订阅专栏

题目链接：http://codeforces.com/problemset/problem/593/B

题意：直线：y=kx+b，给出n个(k,b)，问这n条直线是否在(x1,x2)中有交点

思路：处理处每条直线与x1，x2的交点l和r，存储结构体数组s中，如果li < lj 且 ri>rj则相交，由于数据比较大，需要有更好的查询方式，我们先以l从小到大排一遍序，先以s[0]为基准tmp进行比较，s[tmp].r<=s[i].r的时候，我可以得知在(x1,x2)内与直线tmp有交点，必须先与i有交点，tmp=i，以i为基准继续比较，时间复杂度是O(n)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000300
using namespace std;

struct Node
{
    long long l,r;
}s[maxn];

bool cmp(Node p,Node q)
{
    if (p.l!=q.l) return p.l<q.l;
    else return p.r<q.r;

}


int main()
{
    int n,x1,x2;
    while (scanf("%d",&n)!=EOF)
    {
        scanf("%d%d",&x1,&x2);
        for (int i=0;i<n;i++)
        {
            int k,b;
            scanf("%d%d",&k,&b);
            s[i].l=(long long)k*x1+b;
            s[i].r=(long long)k*x2+b;
        }

        sort(s,s+n,cmp);

        int tmp=0,flag=0;
        for (int i=1;i<n;i++)
        {
            if (s[tmp].l<s[i].l && s[tmp].r>s[i].r)
            {
                flag=1;
                break;
            }
            else
            {
                tmp=i;
            }

        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
}