B. Anton and Lines
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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_1 < _x_2. In other words, is it true that there are1 ≤ 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_1 < x’ < _x_2, that is, point (x’, y’) lies inside the strip bounded by _x_1 < _x_2.
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_1 and _x_2 ( - 1 000 000 ≤ _x_1 < _x_2 ≤ 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 test(s)
input
4
1 2 1 2 1 0 0 1 0 2
output
NO
input
2
1 3 1 0 -1 3
output
YES
input
2
1 3 1 0 0 2
output
YES
input
2
1 3 1 0 0 3
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=
那么li[i].secli[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))
25using namespace std;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int n;
33LL x1,x2;
34pair<ll,ll>li[N];
35
36
37
38int main()
39{
40#ifndef ONLINE_JUDGE
41// freopen("in.txt","r",stdin);
42#endif
43
44scanf("%d",&n);
45scanf("%I64d %I64d",&x1,&x2);
46LL b,k;
47for ( int i = 0 ; i < n ; i++)
48{
49scanf("%I64d %I64d",&k,&b);
50li[i]=make_pair(k*x1+b,k*x2+b);
51}
52sort(li,li+n);
53bool ok = false;
54for ( int i = 1 ; i < n ; i++)
55if (li[i-1].second>li[i].second)
56{
57ok = true;
58break;
59}
60
61if (!ok) puts("NO");
62else puts("YES");
63
64
65
66#ifndef ONLINE_JUDGE
67fclose(stdin);
68#endif
69return 0;
70}