CodeForces 593B Anton and Lines

计算出每条线段在x1处的y坐标和x2处的y坐标。

就下来只要根据每条线段左右两处的y坐标就可以判断是否有交点。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

long long INF=9999999999999999;
long long x1,x2;
int n;
struct X
{
    long long k,b;
    long long yl,yr;
}s[100000+10];

long long Min[100000+10];

bool cmp(const X&a,const X&b)
{
    if(a.yl==b.yl) return a.yr<b.yr;
    return a.yl<b.yl;
}

int main()
{
    scanf("%d",&n);
    scanf("%lld%lld",&x1,&x2);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&s[i].k,&s[i].b);

    for(int i=1;i<=n;i++)
    {
        s[i].yl=s[i].k*x1+s[i].b;
        s[i].yr=s[i].k*x2+s[i].b;
    }


    sort(s+1,s+1+n,cmp);

    for(int i=1;i<=n;i++) Min[i]=INF;
    for(int i=n-1;i>=1;i--)
    {
        if(s[i].yl==s[i+1].yl) Min[i]=Min[i+1];
        else Min[i]=min(Min[i+1],s[i+1].yr);
    }
    bool Find=0;
    for(int i=1;i<=n;i++)
        if(Min[i]<s[i].yr) Find=1;

    if(Find) printf("YES
");
    else printf("NO
");
    return 0;

}