codeforces #329 div 2 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

input

output

YES

input

output

NO

Note

In the first sample there are intersections located on the border of the strip, but there are no intersections located strictly inside it.

好吧。。。人蠢。。所以没想出来。。

其实画个图就能明白。。。如果两条直线相交在x1,x2之间。。

那么两条直线，分别于x1,x2的交点。。一定是一对逆序对。。。

我们可以得到每条直线在x1,x2的交点的纵坐标。。

然后按照与x1交点的纵坐标降序排。

另外一个比较重要的的是，判断是否有逆序对，只需要判断相邻的就行了。

可以用如下证明（不知道有什么更容易想的办法？）

假设直线i与直线i+k(k>=2)相交，那么直线i与直线i+j(1=<j<k)不相交。

那么li[i].sec<li[i+j].sec,li[i].sec>li[i+k].sec

所以li[i+j].sec>li[i].sec>li[i+k].sec

那么直线i+j一定与i+k相交

当j=k-1时，i+j与i+k相邻。

也就是说...如果任意直线i与j相交...我们总可以转化成一对相邻的直线相交。

因此只判断相邻直线的相交就可以。

画图也能看出来。

最后一点是，要开long long 。

 1 /*************************************************************************
 2     > File Name: code/cf/#329/B.cpp
 3     > Author: 111qqz
 4     > Email: rkz2013@126.com 
 5     > Created Time: 2015年11月05日 星期四 15时34分05秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include<iomanip>
10 #include<cstdio>
11 #include<algorithm>
12 #include<cmath>
13 #include<cstring>
14 #include<string>
15 #include<map>
16 #include<set>
17 #include<queue>
18 #include<vector>
19 #include<stack>
20 #include<cctype>
21                  
22 #define lson l,m,rt<<1
23 #define rson m+1,r,rt<<1|1
24 #define ms(a,x) memset(a,x,sizeof(a))
25 using namespace std;
26 const int dx4[4]={1,0,0,-1};
27 const int dy4[4]={0,-1,1,0};
28 typedef long long LL;
29 typedef double DB;
30 const int inf = 0x3f3f3f3f;
31 const int N=1E5+7;
32 int n;
33 LL x1,x2;
34 pair<LL,LL>li[N];
35 
36 
37 
38 int main()
39 {
40   #ifndef  ONLINE_JUDGE 
41 //   freopen("in.txt","r",stdin);
42   #endif
43 
44    scanf("%d",&n);
45    scanf("%I64d %I64d",&x1,&x2);
46    LL b,k;
47    for ( int i = 0 ; i < n ; i++)
48     {
49     scanf("%I64d %I64d",&k,&b);
50     li[i]=make_pair(k*x1+b,k*x2+b);
51     }
52    sort(li,li+n);
53    bool ok = false;
54    for ( int i = 1 ; i < n ; i++)
55        if (li[i-1].second>li[i].second)
56     {
57         ok = true;
58         break;
59     }
60 
61    if (!ok) puts("NO");
62    else puts("YES");
63 
64   
65    
66  #ifndef ONLINE_JUDGE  
67   fclose(stdin);
68   #endif
69     return 0;
70 }

View Code