Codeforces Round #329 (Div. 2)B. Anton and Lines 贪心

B. Anton and Lines

The teacher gave Anton a large geometry homework, but he didn't do it (as usual) as he participated in a regular round on Codeforces. In the task he was given a set of n lines defined by the equations y = ki·x + bi. It was necessary to determine whether there is at least one point of intersection of two of these lines, that lays strictly inside the strip between x1 < x2. In other words, is it true that there are1 ≤ i < j ≤ n and x', y', such that:

y' = ki * x' + bi, that is, point (x', y') belongs to the line number i;
y' = kj * x' + bj, that is, point (x', y') belongs to the line number j;
x1 < x' < x2, that is, point (x', y') lies inside the strip bounded by x1 < x2.

You can't leave Anton in trouble, can you? Write a program that solves the given task.

Input

The first line of the input contains an integer n (2 ≤ n ≤ 100 000) — the number of lines in the task given to Anton. The second line contains integers x1 and x2 ( - 1 000 000 ≤ x1 < x2 ≤ 1 000 000) defining the strip inside which you need to find a point of intersection of at least two lines.

The following n lines contain integers ki, bi ( - 1 000 000 ≤ ki, bi ≤ 1 000 000) — the descriptions of the lines. It is guaranteed that all lines are pairwise distinct, that is, for any two i ≠ j it is true that either ki ≠ kj, or bi ≠ bj.

Output

Print "Yes" (without quotes), if there is at least one intersection of two distinct lines, located strictly inside the strip. Otherwise print "No" (without quotes).

Sample test(s)

input

output

NO

input

output

YES

题意：给你x,y,还有n条直线，问你在x到y的区域内部是否存在交点，不包括x,y上
题解：贪心，我们知道在x,y上必然存在两个交点，所以我们贪心按照左边从小到大排序，如果右边不是递增的则存在交点

///

#include<bits/stdc++.h>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//****************************************

#define maxn 1000000+5

#define mod 1000000007

double  k[maxn],b[maxn];

struct ss{

   double l;

   double r;

   int index;

}G[maxn];

int cmp(ss s1,ss s2){

    if(s1.l==s2.l)return s1.r<s2.r;

  else  return s1.l<s2.l;

}

int n;

int main(){

   n=read();

   double x,y;

   scanf("%lf%lf",&x,&y);

   int kk=;

   for(int i=;i<=n;i++){

    scanf("%lf%lf",&k[i],&b[i]);

        double   xx=k[i]*x+b[i];

        double   yy=k[i]*y+b[i];

        G[++kk].l=xx;G[kk].r=yy;

   }

   sort(G+,G+kk+,cmp);

   double now=-,last=G[].r;

   for(int i=;i<=kk;i++){

          if(G[i].r<last){

            cout<<"YES"<<endl;

            return ;

       }

       now=G[i].l;

       last=G[i].r;

   }

   cout<<"NO"<<endl;

  return ;

}

代码

秒客网

Codeforces Round #329 (Div. 2)B. Anton and Lines 贪心

相关文章