CodeForces - 593B 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 = 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:html

• 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 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 ₁ 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.c++

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.web

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).app

Example Outputide

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

题意
在给出的的直线中（第三行到最后一行是给出的直线），找出是否存在一个svg

交点位于X₁和X₂之间。存在输出“YES”不然输出“NO”。spa

题解
咱们先来分析一下，两条直线相交在X₁和X₂之间须要知足什么条件，我code

画了一个图：
从图上能够看出 $y = x$ 与 $y = -x + 3$ 在X₁ = 1，X₂ = 2之间存在一个
交点……咱们来观察一下这两条直线和X₁、X₂的关系。蓝线与X₁的交点在黄线与X₁的交点的上方，（决定它们的与X₁、X₂的交点的高低只有 y 坐标）而与X₂的交点，蓝线与X₂的交点在黄线的下方。。。这里咱们把直线与X₁、X₂的交点记录下来（只记录 y 坐标就好了）。那么两条直线，分别于 X₁,X₂ 的交点。 必定是一对逆序对。咱们能够获得每条直线在 X₁,X₂ 的交点的纵坐标。而后按照与 X₁ 交点的纵坐标升序排。另一个比较重要的的是，判断是否有逆序对，只须要判断相邻的就好了。orm

能够用以下证实（不知道有什么更容易想的办法？）xml

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

那么 li[i].sec < li[i+j].sec, li[i].sec >l i[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相交…咱们总能够转化成一对相邻的直线相交。

所以只判断相邻直线的相交就能够。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;

ll n,x1,x2;
pair<ll,ll> li[N];

int main()
{
    scanf("%lld",&n);
    scanf("%lld %lld",&x1,&x2);
    for(int i=0;i<n;i++)
    {
        ll k,b;
        scanf("%lld %lld",&k,&b);
        li[i] = make_pair(k*x1+b,k*x2+b);
    }
    sort(li,li+n);

    bool flag = false;
    for(int i=1;i<n;i++)
    {
        if(li[i-1].second > li[i].second) // 由于咱们以前是升序排序，按照与X1的交点从小到大
        								 //排序好了，咱们只要找到（按照排好的序顺序寻找）有一条线与X2
       									 //的交点大于另一条的就表示至少有一个交点在X一、X2之间
        {
            flag = true;
            break;
        }
    }

    if(!flag)
        printf("NO");
    else
        printf("YES");

    return 0;
}