Codeforces Round #329 (Div. 2) B. Anton and Lines （[好题] 计算直线在区间是否有交点）

本文主要是介绍Codeforces Round #329 (Div. 2) B. Anton and Lines （[好题] 计算直线在区间是否有交点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：给出n个条直线，然后在指定的区间(x1,x2)是否有直线的交点存在。
解法：一：闭区间，首先把区间略微调小。
二：计算直线在x1,x2上的交点y坐标，以及直线的id，然后按照y值，id值排序，最后判断第x1,x2左右两边的第i个点是不是同一直线的，如果不是，就存在交点。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100011;
const int inf=1<<27;
const long long mod=751492854;
#define LL long long
#define P pair<int,int>
#define X first
#define Y second
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a));struct node{double y;int id;bool operator<(const node &t) const {return y<t.y||(y==t.y&&id<t.id);}
};
vector<node> A,B;
int main(){int n;scanf("%d",&n);double k,b,x1,x2;node tmp;scanf("%lf%lf",&x1,&x2);if(x1>x2)swap(x1,x2);x1+=1e-8;///题目是闭区间，所以这里微调x2-=1e-8;for(int i=0;i<n;i++){scanf("%lf%lf",&k,&b);tmp.y=k*x1+b;tmp.id=i;A.pb(tmp);tmp.y=k*x2+b;B.pb(tmp);}sort(A.begin(),A.end());sort(B.begin(),B.end());for(int i=0;i<n;i++){if(A[i].id!=B[i].id){puts("YES");return 0;}}puts("NO");return 0;
}

这篇关于Codeforces Round #329 (Div. 2) B. Anton and Lines （[好题] 计算直线在区间是否有交点）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---