Tag:数学
题目描述
【题面大意】
给定 \(n\) 条形如 \(y=k_ix+b_i\) 的直线，你需要判断是否存在两条直线 \(a,b\)，使 \(a,b\) 的交点 \((x_0,y_0)\) 满足 \(x_1<x_0<x_2\)。
【数据规模与约定】
\(1\le n\le 10^5\)，\(-10^6\le x_1,x_2,k_i,b_i\le 10^6\)。
数据保证对于每两条直线 \(i,j(i\ne j)\)，都有 \(k_i\ne k_j\) 或 \(b_i\ne b_j\)。
思路
这道题我们直接求两条直线有没有交点是行不通的，我们不妨把目光聚焦在 \(x1\) 和 \(x2\) 上。
令直线 1 与 \(y=x1\) 和 \(y=x2\) 的交点的横坐标为 \(x2\) 和 \(x3\)，直线 2 与 \(y=x1\) 和 \(y=x2\) 的交点的横坐标为 \(x4\) 和 \(x5\)。
若 \(x2>x4\) 且 \(x3>x5\) 两直线平行，
若 \(x2<x4\) 且 \(x3<x5\) 两直线也平行。
换句话说只要 \(x2\) 和 \(x3\) 的大小关系和 \(x4\) 和 \(x5\) 的大小关系不同，则两直线必有横坐标在 \((x1,x2)\) 的交点。
所以我们把每一条直线与 \(y=x1\) 和 \(y=x2\) 的交点的横坐标算出来，随便按照一个排序，判断另一个是不是逆序的就好了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct st{
double x1,x2;
}a[100005];
int x1,x2;
bool cmp(st a,st b)
{
if(a.x1==b.x1) return a.x2<b.x2;
return a.x1<b.x1;
}
signed main()
{
// freopen("1.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
cin>>x1>>x2;
for(int i=1;i<=n;i++)
{
double k,b;
cin>>k>>b;
a[i].x1=k*x1+b;
a[i].x2=k*x2+b;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<n;i++)
{
if(a[i].x2>a[i+1].x2)
{
cout<<"YES\n";
return 0;
}
}
cout<<"NO\n";
return 0;
}