B. Anton and Lines

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/593/problem/B

Description

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 = k_i·x + b_i. 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 x₁ < x₂. In other words, is it true that there are 1 ≤ i < j ≤ n and x', y', such that:

y' = k_i * x' + b_i, that is, point (x', y') belongs to the line number i;

y' = k_j * x' + b_j, that is, point (x', y') belongs to the line number j;

x₁ < x' < x₂, that is, point (x', y') lies inside the strip bounded by x₁ < x₂.

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 x₁ and x₂ ( - 1 000 000 ≤ x₁ < x₂ ≤ 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 k_i, b_i ( - 1 000 000 ≤ k_i, b_i ≤ 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 k_i ≠ k_j, or b_i ≠ b_j.

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 Input

4 1 2 1 2 1 0 0 1 0 2

Sample Output

NO

HINT

题意

给你一堆直线，然后问你在(x1,x2)区间内，是否有交点

题解：

这道题转化为，在直线交x = x1,x = x2之后，是否存在逆序对

有两个坑点，1.答案会爆long long 2.区间是开区间

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct node{    double x;    int y;};bool cmp(node a,node b){    if(a.x==b.x)        return a.y
          
            Q;vector
           
             P;int main(){ int n;scanf("%d",&n); double x1,x2; cin>>x1>>x2; if(x1>x2)swap(x1,x2); x1 += 1e-8; x2 -= 1e-8; for(int i=1;i<=n;i++) { double k,b; scanf("%lf%lf",&k,&b); node ppp; ppp.x = k*x1+b,ppp.y=i; Q.push_back(ppp); ppp.x = k*x2+b,ppp.y=i; P.push_back(ppp); } sort(Q.begin(),Q.end(),cmp); sort(P.begin(),P.end(),cmp); int flag = 0; for(int i=0;i

转载地址：http://iucjl.baihongyu.com/

你可能感兴趣的文章